Search for a tool
Euler's Totient

Tool to compute Phi: the Euler Totient. Euler's Totient function φ(n) represents the number of integers inferior to n and coprime with n.

Results

Euler's Totient -

Tag(s) : Arithmetics

Share
Share
dCode and you

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!


Please, check our community Discord for help requests!


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

Euler's Totient

Euler's Totient Phi Calculator Phi(N)=?


Display the list of numbers relatively prime with N

Solver for Phi(?)=N (Inverse Phi)


Tool to compute Phi: the Euler Totient. Euler's Totient function φ(n) represents the number of integers inferior to n and coprime with n.

Answers to Questions

What is Euler's totient? (Definition)

Euler's totient (or Eulers totient's function), 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 $

How to calculate phi(n) (Euler's totient)?

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, first 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 $

How to calculate inverse phi(n)?

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)

What is Euler's totient for?

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.

What are Euler's totient properties?

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 $

Source code

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 !

Need Help ?

Please, check our community Discord for help requests!

Questions / Comments

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


Source : https://www.dcode.fr/euler-totient
© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.
Feedback