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

Team dCode likes feedback and relevant comments; to get an answer give an email (not published). It is thanks to you that dCode has the best Euler's Totient tool. Thank you.

# Euler's Totient

## Euler's Totient Phi Calculator

### Display the list of numbers relatively prime with N

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

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

### 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 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 !