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

This script has been updated, please report any problems.

## 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)?

To calculate the value of Euler's Totient, one can realize a prime factor decomposition of n.

$$n=\prod_{i=1}^rp_i^{k_i}$$

With \ (p_i \) prime factors and $$k_i$$ their number of appearance in decomposition.

You can them apply the formula:

$$\varphi(n)=\prod_{i=1}^r(p_i-1)p_i^{k_i-1}=n\prod_{i=1}^r\left(1-\frac1{p_i}\right)$$

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