Euler's Totient Function

Euler's totient function, also known as Euler's phi function, is a mathematical function that counts the number of positive integers that are coprime with a given positive integer $n$. It is named after the Swiss mathematician Leonhard Euler, who introduced it in 1763.

Definition

The totient function is denoted by $\varphi(n)$ and is defined as the number of positive integers less than or equal to $n$ that are coprime with $n$. In other words, $\varphi(n)$ is the number of positive integers $k$ such that $1 \leq k \leq n$ and $\gcd(k, n) = 1$.

For example, let's take $n = 6$. The positive integers less than or equal to 6 are 1, 2, 3, 4, 5, and 6. Out of these, only 1 and 5 are coprime with 6. Therefore, $\varphi(6) = 2$.

Properties

1. If $p$ is a prime number, then $\varphi(p) = p - 1$. This is because all positive integers less than $p$ are coprime with $p$, except for $p$ itself.

2. If $p$ is a prime number and $k$ is a positive integer, then $\varphi(p^k) = p^k - p^{k-1}$. This is because there are $p^k$ positive integers less than or equal to $p^k$, and exactly $p^{k-1}$ of them are not coprime with $p^k$.

3. If $m$ and $n$ are coprime, then $\varphi(mn) = \varphi(m) \varphi(n)$. This follows from the fact that the set of positive integers less than or equal to $mn$ that are coprime with $mn$ can be partitioned into two sets: those that are coprime with $m$ and those that are coprime with $n$.

4. The totient function is multiplicative, which means that if $m$ and $n$ are coprime, then $\varphi(mn) = \varphi(m) \varphi(n)$. This property follows from property 3 and the fact that the totient function is completely multiplicative, which means that if $m$ and $n$ are not necessarily coprime, then $\varphi(mn) = \varphi(m) \varphi(n) \frac{d}{\varphi(d)}$, where $d = \gcd(m, n)$.

Calculation

Calculating the totient function for small numbers is easy, but for large numbers, it can be quite difficult. There are several methods for calculating the totient function, including the following:

1. Brute force: For small values of $n$, one can simply check all positive integers less than or equal to $n$ and count the ones that are coprime with $n$.

2. Prime factorization: If $n$ is a product of distinct primes, say $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$, then $\varphi(n) = (p_1 - 1)p_1^{k_1 - 1}(p_2 - 1)p_2^{k_2 - 1} \cdots (p_r - 1)p_r^{k_r - 1}$.

3. Euler's product formula: This formula expresses the totient function as an infinite product over all prime numbers: $\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$, where the product is taken over all distinct prime divisors of $n$.

Applications

The totient function has many important applications in number theory and cryptography. Here are a few examples:

1. Primality testing: If $n$ is a positive integer and $\varphi(n) = n - 1$, then $n$ is prime.

2. RSA cryptosystem: The security of the RSA cryptosystem is based on the assumption that it is difficult to factorize large integers. The totient function plays a crucial role in this algorithm, as it is used to compute the private key.

3. Primitive roots: A primitive root modulo $n$ is an integer $a$ that generates the multiplicative group of integers modulo $n$. The existence of primitive roots is closely related to the value of the totient function. Specifically, there exists a primitive root modulo $n$ if and only if $n$ is of the form $2, 4, p^k$, or $2p^k$, where $p$ is an odd prime and $k$ is a positive integer.

Conclusion

Euler's totient function is a fascinating and important topic in number theory, with many interesting properties and applications. It is a fundamental concept that underlies many modern cryptographic systems, and its study continues to be an active area of research in mathematics.

Links

オイラー関数[JA]