Two integers are coprime, relatively prime, or mutually prime if the only positive integer that is a divisor of them both is 1.
Euler's totient function, also known as the phi function, is a mathematical function that takes in an integer and returns the number of positive integers less than that integer that are relatively prime to it.
For example, if we take the integer 6, the positive integers less than 6 that are relatively prime to it are 1, 5, and 2. Therefore, the value of Euler's totient function when applied to 6 is 3.
The function can also be defined as the number of integers k in the range 1≤k≤n in which the greatest common divisor gcd(n,k) is equal to 1.
The phi function of a prime number is always equal to the prime number minus 1. This is because a prime number is only divisible by 1 and itself, so it has exactly two relatively prime numbers less than it.
The function can be computed using the formula:
$$ \phi(n) = n \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \times \dots \times \left(1 - \frac{1}{p_k}\right) $$
where n is the number that the function is applied to, and p1, p2, ..., pk are the distinct prime factors of n.
Euler's totient function is used in many areas of mathematics and computer science, including number theory, cryptography, and coding theory.
If P1 & P2 are two coprime numbers then φ(P1*P2)=φ(P1)*φ(P2).
φ(P) = P-1 if P is a prime number.n=P1*P2 and P1 and P2 are co-primes then, φ(n)=(P1–1)*(P2–1).Euler’s theorem states that if a and n are relatively prime then, pow(a, φ(n)) = 1 mod n.
Fermat’s little theorem states that, if p is a prime number, then for any integer a, the number pow(a, p) - a is an integer multiple of p.
pow(a, p) is equivalent to a mod p.If a is not divisible by p, Fermat’s little theorem is equivalent to, pow(a, p-1) - 1 which is an integer multiple of p.