Tool to compute Phi: Euler Totient. Euler's Totient φ(n) is a number representing the number of integers inferior to n, relatively prime with n.

Euler's Totient - dCode

Tag(s) : Mathematics,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*!

This page is using the new English version of dCode, *please make comments* !

Sponsored ads

Tool to compute Phi: Euler Totient. Euler's Totient φ(n) is a number representing the number of integers inferior to n, relatively prime with n.

The value of \( \varphi(n) = \phi(n) = phi(n) \) is computed 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, you must know the prime factor decomposition of \( n \). Consider \( p_i \) 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 \) you get: $$ \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 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 $$

n=7, a=3 and phi(7) = 6 so 3^6 = 729 = 1 modulo 7

This theorem is the basis of the RSA encryption.

dCode retains ownership of the source code of the script Euler's Totient. 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, etc.) which dCode owns rights can be transferred after sales quote. So if you need to download the Euler's Totient script for offline use, for you, your company or association, see you on contact page !

euler,totient,phi,prime,divisor,number,relatively

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

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