Sooji Shin

Let n be a positive integer. Recall that the Euler phi-function φ(n) is defined as the number of positive integers less than or equal to n and relatively prime to n. Note that φ(1)=1. We have seen that Euler used this function to generalize the Fermat's Little Theorem. (See 71st article.) It is sometimes needed to calculate the value φ(n) of given integer n. In this article, we observe some properties of Euler phi-function and how to calculate the value φ(n).

Definition 1.  A function whose domain is the set of natural numbers N and range is a subset of set of the real numbers R is called a number-theoric function or an arithmetic function.

Definition 2.  By multiplicative function we mean an arithmetic function f that satisfies the following two conditions:
(i) f(1)=1;
(ii) if (m, n)=1, that is, m and n are relatively primes, then f(mn)=f(m)f(n).

Theorem 3.  If p is a prime and k is a positive integer then φ(p^k) = p^k-p^k-1 holds.
Proof.  Observe that (a, p^k)=1 iff (a, p)=1 iff ~(p|a). Moreover, the number of multiples of p in 0p, 1p, 2p, …, p^k-p is p^k-1. Hence we have φ(p^k) = p^k-p^k-1.  QED.

Lemma 4.  If m and n are positive relative primes then the function f : Z_mn→ Z_m × Z_n defined as f(a)=(<a>_m, <a>_n) is an one-to-one correspondence.

Proof.  By the Chinese Remainder Theorem, for each r∈Z_m and s∈Z_n there exists the unique solution x≡u (mod mn) for the simultaneus equation x≡r (mod m) and x≡s (mod n). Let a be the remainder of u divided by mn then we have a≡u (mod mn), thus we have f(a)=(r, s). Hence f is onto, that is, f is surjective. Furthermore, for |Z_mn|=mn=|Z_m||Z_n|=|Z_m×Z_n|, if is into, that is, f is injective.  QED.

Now we use the notation Z_n^* = {r∈Z_n|(r, n)=1} for convinience. Then we can define Euler phi-function as φ(n) = |Z_n^*|.

Lemma 5.  If m and n a re positive relative primes then |Z_mn^*|=|Z_m^*||Z_n^*|, that is, φ(mn)=φ(m)φ(n).

Proof.  By Lemma 4, f : Z_mn→ Z_m × Z_n defined as f(a)=(<a>_m, <a>_n) is an one-to-one correspondence. For each a∈Z_mn, (a, mn)=1 holds if and only if (a, m)=(a, n)=1. Moreover, for a≡<a>_m (mod m) and a≡<a>_n (mod n), we have gcd(<a>_m, m) = gcd(a, m) and gcd(<a>_n, n) = gcd(a, n). Thus for each a∈Z_mn, (a, mn)=1 holds if and only if (<a>_m ,m)=(<a>_n, n)=1. Hence we have |Z_mn^*|=|Z_m^*||Z_n^*|.  QED.

Combining Theorem 3 and Lemma 5, we have the following theorem.

Theorem 6.  Euler phi-function is multiplicative. Furthermore, if a positive integer m is factorized as n=p₁^e1p₁^e2…p₁^er then φ can be calculated by φ(n)=(p₁^e1-p₁^e1-1)(p₂^e2-p₂^e2-1)…(p_r^er-p_r^er-1)=m(1- 1/p₁)(1 - 1/p₂)…(1 - 1/p_r).

As an example, we have:
φ(2160) = φ(2⁴×3³×5) = 2³×(3³-3²)×4 = 8×18×4 = 576.

Geschrieben von Sooji Shin