Euler Totient Function Calculator
Euler Totient Function Calculator computes \\( \phi(n) \\), the number of integers up to \\( n \\) that are coprime to \\( n \\), and plots the function for a range of values.
Euler Totient Function
The Euler Totient Function \\( \phi(n) \\) counts the number of integers from 1 to \\( n \\) that are coprime to \\( n \\) (i.e., \\( \gcd(k, n) = 1 \\)).
Formula:
For a positive integer \\( n \\) with prime factorization \\( n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \\),
\\[ \phi(n) = n \prod_{p \mid n} \left(1 – \frac{1}{p}\right) \\]Where:
- \\( p \\): Distinct prime factors of \\( n \\)
- \\( e_i \\): Exponent of prime \\( p_i \\)
Properties:
- For a prime \\( p \\), \\( \phi(p) = p – 1 \\).
- For a prime power \\( p^e \\), \\( \phi(p^e) = p^e – p^{e-1} \\).
- For coprime integers \\( m \\) and \\( n \\), \\( \phi(mn) = \phi(m) \phi(n) \\).
Examples
Example 1
Input: \\( n = 6 \\)
\\[
\phi(6) = \phi(2 \cdot 3) = 6 \left(1 – \frac{1}{2}\right) \left(1 – \frac{1}{3}\right) = 6 \cdot \frac{1}{2} \cdot \frac{2}{3} = 2
\\]
Coprime numbers: \\( \{1, 5\} \\)
Example 2
Input: \\( n = 8 \\)
\\[
\phi(8) = \phi(2^3) = 2^3 – 2^{3-1} = 8 – 4 = 4
\\]
Coprime numbers: \\( \{1, 3, 5, 7\} \\)
Example 3
Input: \\( n = 15 \\)
\\[
\phi(15) = \phi(3 \cdot 5) = 15 \left(1 – \frac{1}{3}\right) \left(1 – \frac{1}{5}\right) = 15 \cdot \frac{2}{3} \cdot \frac{4}{5} = 8
\\]
Coprime numbers: \\( \{1, 2, 4, 7, 8, 11, 13, 14\} \\)