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.

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

# Euler's Totient

## Euler's Totient Phi 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.

## Answers to Questions

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

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

### 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^{\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.

## Source code

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 !

## Questions / Comments

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.

Source : http://www.dcode.fr/euler-totient
© 2017 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode