Euler’s phi function, part 2

This is the part 2 of an introductory discussion on Euler’s phi function. See part 1 for a background discussion on the phi function $\phi$.

In computing modular arithmetic where the modulus is $m$, the following two sets of integers are of interest.

$\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$

$(\mathbb{Z}_m)^*=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\}$

The first set $\mathbb{Z}_m$ is a representative set under the arithmetic modulo $m$ since every integer is congruent mod $m$ to exactly one number in $\mathbb{Z}_m$. In many settings, the only results of interest for modulo $m$ calculations are values in $\mathbb{Z}_m$ (also called least residues).

The second set $(\mathbb{Z}_m)^*$ consists of all integers in $\mathbb{Z}_m$ that are relatively prime to the modulus $m$ (as the set is defined). So any integer that is relatively prime to the modulus $m$ is congruent to exactly one number in $(\mathbb{Z}_m)^*$. Furthermore, the set $(\mathbb{Z}_m)^*$ is closed under multiplication modulo $m$. It is also the case that every number in $(\mathbb{Z}_m)^*$ has a multiplicative inverse modulo $m$. If we look for numbers a where $a^n \equiv 1 \ (\text{mod} \ m)$, we do not need to look further than the set $(\mathbb{Z}_m)^*$. We have the following theorem.

Theorem 1

Let $a$ be an integer in $\mathbb{Z}_m$. The following conditions are equivalent.

1. $\text{GCD}(a,m)=1$.
2. There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$.
3. Some positive power of $a$ modulo $m$ is $1$, i.e., $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$.

$\text{ }$

The proof of Theorem 1 is found in Euler’s phi function, part 1.

Euler’s phi function $\phi(m)$ is defined to be the number of elements in the set $(\mathbb{Z}_m)^*$. In this post, we prove two elementary properties of the function $\phi$. We have the following two results.

Theorem 2

Let $p$ be a prime number. Let $n$ be a positive integer. Then $\phi(p^n)=p^{n-1}(p-1)$.

Theorem 3

Let $m$ and $n$ be two positive integers that are relatively prime. Then $\phi(m n)=\phi(m) \cdot \phi(n)$.

Example

Before proving the theorems, we work some examples. Find $\phi(299376)$. We factor $299376$ into its prime factors.

$299376=2^4 \cdot 3^5 \cdot 7 \cdot 11$

By Theorem 3, the function $\phi$ is multiplicative among integers that are relatively prime. Now we have $\phi(299376)=\phi(2^4) \cdot \phi(3^5) \cdot \phi(7) \cdot \phi(11)$. Applying Theorem 2, we have:

\displaystyle \begin{aligned} \phi(299376)&=\phi(2^4) \cdot \phi(3^5) \cdot \phi(7) \cdot \phi(11) \\&=2^3 (2-1) \cdot 3^4 (3-1) \cdot (7-1) \cdot (11-1) \\&=8 \cdot 162 \cdot 6 \cdot 10 \\&=77760 \end{aligned}

Proof of Theorem 2

Among the integers $1,2,3,\cdots, p^n-1,p^n$, the only ones that are not relatively prime to $p^n$ are multiples of $p$ (since $p$ is a prime number). There are $p^{n-1}$ many multiples of $p$. They are:

$p, 2 \cdot p, 3 \cdot p, \cdots, p^{n-1} \cdot p$

Thus among the integers $1,2,3,\cdots, p^n-1,p^n$, the number of integers that are relatively prime to $p^n$ must be $\phi(p^n)=p^n-p^{n-1}=p^{n-1}(p-1)$. $\blacksquare$

Lemma 4 will be helpful in proving Theorem 3.

Lemma 4

If $a$ is relatively prime to $m$ and $a$ is relatively prime to $n$, then $a$ is relatively prime to $mn$.

Proof of Lemma 4

Since $a$ is relatively prime to $m$, their greatest common divisor is one. Using the extended Euclidean algorithm, $ax+my=1$ for some integers $x$ and $y$. Since $a$ is relatively prime to $n$, $ah+nk=1$ for some integers $h$ and $k$. Multiplying these two equations, we get:

$(ax+my) \cdot (ah+nk)=a(xah+xnk+myh)+mn(yk)=1$

The above equation means that $a(xah+xnk+myh) \equiv 1 \ (\text{mod} \ mn)$. This shows that $xah+xnk+myh$ is the multiplicative inverse of $a$ modulo $mn$. By Theorem 1, $a$ is relatively prime to $mn$. $\blacksquare$

Proof of Theorem 3

Suppose $m$ and $n$ are relatively prime. We show that among the integers $1,2,3,\cdots,mn-1,mn$, there are exactly $\phi(m) \cdot \phi(n)$ many numbers that are relatively prime to $mn$. To facilitate the argument, we enumerate the integers $1,2,3,\cdots,mn-1,mn$ as in the following matrix.

$\displaystyle \begin{bmatrix} 1&\text{ }&1 \cdot m+1&\text{ }&2 \cdot m+1&\text{ }&\cdots&k \cdot m+1&\cdots&(n-1) \cdot m+1 \\\text{ }&\text{ }&\text{ } \\2&\text{ }&1 \cdot m+2&\text{ }&2 \cdot m+2&\text{ }&\cdots&k \cdot m+2&\cdots&(n-1) \cdot m+2 \\\text{ }&\text{ }&\text{ } \\3&\text{ }&1 \cdot m+3&\text{ }&2 \cdot m+3&\text{ }&\cdots&k \cdot m+3&\cdots&(n-1) \cdot m+3 \\\text{ }&\text{ }&\text{ } \\\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ }&\cdots&\text{ }&\cdots \\\text{ }&\text{ }&\text{ } \\h&\text{ }&1 \cdot m+h&\text{ }&2 \cdot m+h&\text{ }&\cdots&k \cdot m+h&\cdots&(n-1) \cdot m+h \\\text{ }&\text{ }&\text{ } \\\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ }&\cdots&\text{ }&\cdots \\\text{ }&\text{ }&\text{ } \\m&\text{ }&1 \cdot m+m&\text{ }&2 \cdot m+m&\text{ }&\cdots&k \cdot m+m&\cdots&(n-1) \cdot m+m \end{bmatrix}$

There are $m$ rows and $n$ columns in the matrix. The first observation is that if the first number of a row is $h$ and if $h$ and $m$ are not relatively prime, then there is $d>1$ that is a common divisor of $h$ and $m$. Then $d$ also divides any other number on that row. So if the first number of a row is $h$ and if $h$ and $m$ are not relatively prime, then any number on the $h^{th}$ row is not relatively prime to $m$, hence is not relatively prime to $mn$.

Based on the above observation, to look for numbers that are relatively prime to $mn$, we only need to look at rows where the first number $h$ is relatively prime to $m$. There are exactly $\phi(m)$ many such rows.

We claim that in each of these $\phi(m)$ rows, there are exactly $\phi(n)$ many numbers that are relatively prime to $mn$. It follows that there are exactly $\phi(m) \cdot \phi(n)$ many numbers in the entire matrix that are relatively prime to $mn$. Thus the theorem will be established.

To establish the claim in the above paragraph, consider one such row where the first number $h$ is relatively prime to $m$. First observe that the $n$ numbers in the $h^{th}$ row are distinct congruent modulo $m$. Suppose that $k \cdot m+h \equiv j \cdot m+h \ (\text{mod} \ n)$. Cancel out $h$, we have $k \cdot m \equiv j \cdot m \ (\text{mod} \ n)$. Since $m$ and $n$ are relatively prime, we can cancel out $m$ and obtain $k \equiv j \ (\text{mod} \ n)$. Since both $k$ and $j$ are less than $n$, it must be that $k=j$. So if $k \ne j$, $k \cdot m+h \not \equiv j \cdot m+h \ (\text{mod} \ n)$.

Based on the observation in the above paragraph, the least residues modulo $n$ of the numbers in the $h^{th}$ row must be the set $\left\{0,1,2,\cdots,n \right\}$. This follows from the fact that the $n$ numbers in the $h^{th}$ row are distinct congruent modulo $n$. Hence their least residues must be $n$ distinct numbers too.

So in terms of congruence modulo $n$, the $h^{th}$ row in the matrix is a mirror image of the least resides $\left\{0,1,2,\cdots,n \right\}$. There are exactly $\phi(n)$ many least residues that are relatively prime to $n$. Likewise, there are exactly $\phi(n)$ many numbers in the $h^{th}$ row that are relatively prime to $n$. Furthermore, every number in the $h^{th}$ row is relatively prime to $m$. By Lemma 4, there are exactly $\phi(n)$ many numbers in the $h^{th}$ row that are relatively prime to $mn$. Thus the above claim is established. It follows that the theorem is established. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$