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 more

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!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Feedback and suggestions are welcome so that dCode offers the best 'Euler's Totient' tool for free! Thank you!

# Euler's Totient

## Solver for Phi(?)=N (Inverse Phi)

### What is Euler's totient? (Definition)

Euler's totient function (or Euler's indicator), noted with the greek letter phi: $\varphi(n)$ or $\phi(n)$ an arithmetic function which associates with each strictly positive natural number $n$, the number of natural numbers between 1 and $n$ that are coprime with $n$.

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

Phi(n) (euler indicator) is determined in several ways. The best-known calculation formula for determining the value of the Euler indicator uses the decomposition into prime factors of $n$. Let $p_i$ be the $m$ distinct prime factors that are divisor or $n$ (of multiplicity $k$). Formula (1) is:

$$\varphi(n) = \prod_{i=1}^m (p_i-1) p_i^{k_i-1} \quad\quad (1)$$

After simplification, another formula (2) is:

$$\varphi(n) = n \prod_{i=1}^m \left( 1 - \frac{1}{p_i} \right) \quad\quad (2)$$

Example: For $n = 12$, only $1,\ 5,\ 7,\ 11$ are coprime with $12$ so $\varphi(12) = 4$. The prime factor decomposition of 12 is $12 = 2^2 \times 3^1$

Formula (1) $$\varphi(12) = \left( (2-1) \times 2^{2-1} \right) \times \left( (3-1) \times 3^{1-1} \right) = 2 \times 2 = 4$$

Formula (2) $$\varphi(12) = 12 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 12 \times \frac{2}{6} = \frac{24}{6} = 4$$

### How to calculate phi(n) if n is prime?

If $n$ is a prime number, then $\varphi(n) = n-1$

### How to calculate inverse phi(n)?

Solving $\phi(x) = N$ requires an optimized search algorithm based on $\phi(x) \geq \sqrt{\frac{x}{2}}$ that tests all values. More details here

### What is Euler's totient for (Euler's theorem)?

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$

— $\varphi(ab) = \varphi(a) \varphi(b) \frac{d}{\varphi(d)}$ with $d$ the GCD of $a$ and $b$

— If $a$ and $b$ are coprimes (relatively primes), then $\varphi(a \times b) = \varphi(a) \times \varphi(b)$

— If $a$ divides $b$ then $\varphi(a) \mid \varphi(b)$

— If $a$ is even, $\varphi(2a) = 2 \varphi(a)$

— If $a$ is odd, $\varphi(2a) = \varphi(a)$

The sequence of values of Phi(n) is 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, etc. here

### What is the algorithm for phi(n)?

The Euler phi(n) calculation can be coded with an algorithm like:function phi(n) { r = n; for (i = 2; i*i <= n; i++) { if (n % i == 0) { r -= r / i; while (n % i == 0) { n /= i; } } } if (n > 1) r -= r / n; return r;}

## Source code

dCode retains ownership of the "Euler's Totient" source code. Except explicit open source licence (indicated Creative Commons / free), the "Euler's Totient" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Euler's Totient" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Euler's Totient" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.

## Cite dCode

The copy-paste of the page "Euler's Totient" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Euler's Totient on dCode.fr [online website], retrieved on 2024-09-10, https://www.dcode.fr/euler-totient

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!