Tool to compute Phi: the Euler Totient. Euler's Totient function φ(n) represents the number of integers inferior to n and coprime with n.
Euler's Totient - dCode
Tag(s) : Arithmetics
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
Euler's totient function (or Euler's indicator), noted with the greek letter phi: $ \varphi(n) $ or $ \phi(n) $ an arithmetic function which associates with each strictly positive natural number $ n $, the number of natural numbers between 1 and $ 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 that are divisor or $ 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) $$
Example: For $ n = 12 $, only $ 1,\ 5,\ 7,\ 11 $ are coprime with $ 12 $ so $ \varphi(12) = 4 $. The prime factor decomposition of 12 is $ 12 = 2^2 \times 3^1 $
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 $$
Example: $ n=7 $ , $ a=3 $ and $ \varphi(7) = 6 $ so $ 3^6 = 729 \equiv 1 \mod 7 $
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;
}
}
}
if (n > 1) r -= r / n;
return r;
}
dCode retains ownership of the "Euler's Totient" source code. Except explicit open source licence (indicated Creative Commons / free), the "Euler's Totient" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Euler's Totient" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Euler's Totient" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.
The copy-paste of the page "Euler's Totient" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Euler's Totient on dCode.fr [online website], retrieved on 2024-11-12,