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*!

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

dCode retains ownership of the online 'Euler's Totient' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (PHP, Java, C#, Python, Javascript, Matlab, etc.) no data, script or API access will be for free, same for Euler's Totient download for offline use on PC, tablet, iPhone or Android !

Please, check our community Discord for help requests!

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

▲