Search for a tool
Euler's Totient

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.

Results

Euler's Totient -

Tag(s) : Mathematics,Arithmetics

dCode and you

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!

Team dCode read all messages and answer them if you leave 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 Calculator

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

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.

### How to calculate phi(n) (Euler's totient)?

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

### What is Euler's totient for?

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.