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!

Thanks to your feedback and relevant comments, dCode has developed the best 'Euler's Totient' tool, so feel free to write! 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)$ 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, the first step is to find the prime factor decomposition of $n$. If $p_i$ are the $m$ distinct prime factors divisors 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$

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

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

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

## Source code

dCode retains ownership of the online "Euler's Totient" source code. Except explicit open source licence (indicated CC / Creative Commons / free), the "Euler's Totient" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, 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, copy-paste, or API access for "Euler's Totient" are not public, same for offline use on PC, tablet, iPhone or Android ! Remainder : dCode is free to use.

## Need Help ?

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