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) $ is the value representing the number of integers less than $ n $ that are coprime with $ n $

Euler Phi totient calculator computes the value of Phi(n) in several ways, the best known formula is $$ \varphi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right) $$

where $ p $ is a prime factor which divides $ n $.

To calculate the value of the Euler indicator/totient, the first step is to find the prime factor decomposition of $ n $. If $ p_i $ are the $ m $ distinct prime factors divisors of $ n $, then the formula becomes:

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

For $ n = 6 $, only the numbers $ 1 $ and $ 5 $ are coprime with $ 6 $ so $ \varphi(6) = 2 $. This is confirmed by the formula for $ n = 6 = 2^1 \times 3^1 $, as: $$ \varphi(6) = 6 (1-\frac{1}{2}) (1-\frac{1}{3}) = 2 $$

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}} $ and test all values. More details here (link)

**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) $

dCode retains ownership of the online "Euler's Totient" source code. Except explicit open source licence (indicated CC / Creative Commons / free), the "Euler's Totient" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, 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, copy-paste, or API access for "Euler's Totient" are not public, same for offline use on PC, tablet, iPhone or Android ! Remainder : dCode is free to use.

Please, check our dCode Discord community for help requests!

NB: for encrypted messages, test our automatic cipher identifier!

euler,totient,indicator,phi,prime,divisor,number,function

Source : https://www.dcode.fr/euler-totient

© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲
Thanks to your feedback and relevant comments, dCode has developed the best 'Euler's Totient' tool, so feel free to write! Thank you!