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 more

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 dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!


Thanks to your feedback and relevant comments, dCode has developed 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)


Answers to Questions (FAQ)

What is Euler's totient? (Definition)

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 $

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

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's theorem)?

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 $

— $ \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) $

Source code

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.

Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Questions / Comments

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


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