Euler's Totient

Euler's totient function (or Euler's indicator), noted with the greek letter phi: $ \varphi(n) $ or $ \phi(n) $ is the value representing the number of integers less than $ n $ that are coprime with $ n $

Phi(n) (euler indicator) is determined in several ways. The best-known calculation formula for determining the value of the Euler indicator uses the decomposition into prime factors of $ n $. Let $ p_i $ be the $ m $ distinct prime factors dividing $ n $ (of multiplicity $ k $). Formula (1) is:

$$ \varphi(n) = \prod_{i=1}^m (p_i-1) p_i^{k_i-1} \quad\quad (1) $$

After simplification, another formula (2) is:

$$ \varphi(n) = n \prod_{i=1}^m \left( 1 - \frac{1}{p_i} \right) \quad\quad (2) $$

Formula (1) $$ \varphi(12) = \left( (2-1) \times 2^{2-1} \right) \times \left( (3-1) \times 3^{1-1} \right) = 2 \times 2 = 4 $$

Formula (2) $$ \varphi(12) = 12 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 12 \times \frac{2}{6} = \frac{24}{6} = 4 $$

If $ n $ is a prime number, then $ \varphi(n) = n-1 $

Solving $ \phi(x) = N $ requires an optimized search algorithm based on $ \phi(x) \geq \sqrt{\frac{x}{2}} $ that tests all values. More details here

Euler totient phi function is used in modular arithmetic. It is used in Euler's theorem:

If $ n $ is an integer superior or equal to 1 and $ a $ an integer coprime with $ n $, then $$ a^{\varphi(n)} \equiv 1 \mod n $$

This theorem is the basis of the RSA encryption.

The Euler indicator is an essential function of modular arithmetic:

— A positive integer $ p $ is a prime number if and only if $ \varphi(p) = p - 1 $

— The value $ \varphi(n) $ is even for all $ n > 2 $

— $ \varphi(ab) = \varphi(a) \varphi(b) \frac{d}{\varphi(d)} $ with $ d $ the GCD of $ a $ and $ b $

— If $ a $ and $ b $ are coprimes (relatively primes), then $ \varphi(a \times b) = \varphi(a) \times \varphi(b) $

— If $ a $ divides $ b $ then $ \varphi(a) \mid \varphi(b) $

— If $ a $ is even, $ \varphi(2a) = 2 \varphi(a) $

— If $ a $ is odd, $ \varphi(2a) = \varphi(a) $

The sequence of values of Phi(n) is 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, etc. here

The Euler phi(n) calculation can be coded with an algorithm like:
function phi(n) {
r = n;
for (i = 2; i*i <= n; i++) {
if (n % i == 0) {
r -= r / i;
while (n % i == 0) {
n /= i;
}
}
}
r -= r / n;
return r;
}