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

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

**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 source code of the script Euler's Totient online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be released for free. To download the online Euler's Totient script for offline use on PC, iPhone or Android, ask for price quote on contact page !

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

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

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

Feedback

▲