EulerTotientFunktion

The Euler totient function, denoted by the Greek letter phi ($\phi$) or Euler's phi function, is an arithmetic function that counts the number of positive integers less than or equal to a given positive integer $n$ that are relatively prime to $n$. Two integers are relatively prime if their greatest common divisor (GCD) is 1. For example, $\phi(9)$ counts the numbers from 1 to 9 that share no common factors with 9 other than 1. These numbers are 1, 2, 4, 5, 7, and 8, so $\phi(9) = 6$.

The Euler totient function is multiplicative, meaning that if $a$ and $b$ are coprime integers, then $\phi(ab) = \phi(a)\phi(b)$. This property is crucial for calculating the function. If the prime factorization of $n$ is given by $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$, where $p_i$ are distinct prime numbers and $k_i$ are positive integers, then the formula for the Euler totient function is $\phi(n) = n \prod_{i=1}^{r} (1 - \frac{1}{p_i})$. This can also be expressed as $\phi(n) = p_1^{k_1-1}(p_1-1) p_2^{k_2-1}(p_2-1) \cdots p_r^{k_r-1}(p_r-1)$.

A fundamental property related to the Euler totient function is Euler's theorem, which states that if $a$ and $n$ are coprime positive integers, then $a^{\phi(n)} \equiv 1 \pmod{n}$. This theorem has significant applications in number theory and cryptography. The Euler totient function is also fundamental in the study of cyclic groups and primitive roots.