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

Euler's Totient - dCode

Tag(s) : Arithmetics

dCode is free and its tools are a valuable help in games, puzzles and problems to solve every day!

You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? *Contact-me*!

Sponsored ads

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

Euler's totient, noted with the greek letter phi : \( \phi(n) \) or \( \varphi(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 \( \varphi(n) = \phi(n) = 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^{\phi(n)} \equiv 1 \mod n $$

Example: n=7, a=3 and phi(7) = 6 so 3^6 = 729 = 1 modulo 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 \( \phi(p) = p - 1 \)

- The value \( \phi(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 given for free. So if you need to download the online Euler's Totient script for offline use, check contact page !

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

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

© 2018 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode

Feedback