# Euler’s phi function is multiplicative

This post gives a proof that Euler’s phi function is multiplicative. The proof is a simpler and more elegant proof, as compared to the one presented here. The combinatorial argument is greatly simplified using the Chinese remainder theorem (abbreviated CRT).

The letter $m$ is used below to denote the modulus in modular arithmetic. The phi function $\phi(m)$ is defined to be the count of all the integers $0 \le a \le m-1$ such that $a$ and $m$ are relatively prime. If $m$ is prime, then $\phi(m)=m-1$ since all integers from $1$ to $m-1$ have no factors in common with $m$ (other than 1). If $m=10$, then $\phi(10)=4$ since 1, 3, 7, and 9 are the only numbers that are relatively prime to $m=10$.

To properly work with the phi function, conmsider the following setting. Given a modulus $m$, a set of interest is $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$. This is the set of all least resdues modulo $m$, i.e., every integer is congruent modulo $m$ to exactly one element of $\mathbb{Z}_m$. Another set of interest is $\mathbb{Z}_m^*$, which is the set of all elements $a$ in $\mathbb{Z}_m$ such that $a$ and $m$ are relatively prime. In other words, $\phi(m)$ is defined to be the cardinality of the set $\mathbb{Z}_m^*$.

The set $\mathbb{Z}_m$ is called the ring of integers modulo $m$ since it satisfies the definition of a ring with regard to addition and multiplication modulo $m$. The set $\mathbb{Z}_m^*$ with the multiplication modulo $m$ is a group, i.e. every element of $\mathbb{Z}_m^*$ has a multiplicative inverse with respect to the binary operation of multiplication modulo $m$. The set $\mathbb{Z}_m^*$ is called the multiplicative group of integers modulo $m$. The fact that $\mathbb{Z}_m^*$ is a group is established by the following theorem, which is proved here.

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

1. The numbers $a$ and $m$ are relatively prime, i.e. $\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$.

Another interesting fact to point out is that when $m$ is a prime number, $\mathbb{Z}_m$ is a field, i.e. it is a commutative ring in which every non-zero element has a multiplicative inverse. Another terminology that is used by some authors is that the elements in $\mathbb{Z}_m$ that have multiplicative inverses are called units. Thus $\mathbb{Z}_m^*$ is also called the group of units of the ring of integers modulo $m$. Our notation here is not standard. The usual notation for the ring $\mathbb{Z}_m$ is $\mathbb{Z}/m\mathbb{Z}$. The usual notation for $\mathbb{Z}_m^*$ is $(\mathbb{Z}/m\mathbb{Z})^*$.

The phi function is multiplicative in the following sense.

Theorem 2
Let $m$ and $n$ be positive integers such that they are relatively prime. Then $\phi(m \times n)=\phi(m) \times \phi(n)$.

Theorem 2 is established by the following results.

Lemma 3
Let $m$ and $n$ be positive integers such that they are relatively prime. Then the set $\mathbb{Z}_{mn}$ and the set $\mathbb{Z}_m \times \mathbb{Z}_n$ have the same cardinality.

Proof
To prove that the two sets have the same cardinality, we define a bijection $f: \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n$, i.e. $f$ is a one-to-one function that maps $\mathbb{Z}_{mn}$ onto the set $\mathbb{Z}_m \times \mathbb{Z}_n$. For each $a \in \mathbb{Z}_{mn}=\left\{0,1,2,\cdots,m \cdot n-1 \right\}$, define $f(a)=(c, d)$ where $c \in \mathbb{Z}_m$ with $c \equiv a \ (\text{mod} \ m)$ and $d \in \mathbb{Z}_n$ with $d \equiv a \ (\text{mod} \ n)$.

To see that $f$ is one-to-one, let $f(a)=f(b)$. Then we have $a \equiv b \ (\text{mod} \ m)$ and $a \equiv b \ (\text{mod} \ n)$. By the Chinese remainder theorem, $a \equiv b \ (\text{mod} \ mn)$. Since $a,b \in \mathbb{Z}_{mn}$, $a=b$.

To show that $f$ maps $\mathbb{Z}_{mn}$ onto the set $\mathbb{Z}_m \times \mathbb{Z}_n$, let $(c,d) \in \mathbb{Z}_m \times \mathbb{Z}_n$. Consider the equations $x \equiv c \ (\text{mod} \ m)$ and $x \equiv d \ (\text{mod} \ n)$. By CRT, these two equations have a simultaneous solution $a$ that is unique modulo $m \times n$. This means that $f(a)=(c, d)$. $\square$

Lemma 4
Let $m$ and $n$ be positive integers such that they are relatively prime. Then the set $\mathbb{Z}_{mn}^*$ and the set $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$ have the same cardinality.

Proof
The same mapping $f$ defined in the proof of Lemma 3 is used. We show that when $f$ is restricted to the set $\mathbb{Z}_{mn}^*$, it is a bijection from $\mathbb{Z}_{mn}^*$ onto the set $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. First, we show that for any $a \in \mathbb{Z}_{mn}^*$, $f(a)$ is indeed in $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. To see this, note that $a$ and $m \times n$ are relatively prime. So it must be that $a$ and $m$ are relatively prime too and that $a$ and $n$ are relatively prime.

The function $f$ is one-to-one as shown above. The remaining piece is that for each $(c,d) \in \mathbb{Z}_m^* \times \mathbb{Z}_n^*$, there is some $a \in \mathbb{Z}_{mn}^*$ such that $f(a)=(c,d)$. As in the proof of Lemma 3, there is some $a \in \mathbb{Z}_{mn}$ such that $f(a)=(c,d)$. Note that $a$ and $m$ are relatively prime and $a$ and $n$ are relatively prime. This means that $a$ and $m \times n$ are relatively prime (see Lemma 4 here). Thus the function $f$ is a one-to-one from $\mathbb{Z}_{mn}^*$ onto $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. $\square$

Proof of Theorem 2
Lemma 4 shows that the set $\mathbb{Z}_{mn}^*$ and the set $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$ have the same cardinality. First, $\phi(m \times n)$ is the cardinality of the set $\mathbb{Z}_{mn}^*$. Theorem 2 is established by noting that $\phi(m) \times \phi(n)$ is the cardinality of $\mathbb{Z}_m^* \times \mathbb{Z}_n^*$. $\square$

____________________________________________________________________________

Evaluating the phi function

The combinatorial argument for $\phi(m \times n)=\phi(m) \times \phi(n)$ is greatly simplified by using the Chinese remainder theorem. Compare the above proof with the lengthier proof in an earlier post (see Theorem 3 here). With the multiplicative property of the phi function, we can evaluate the phi function for any positive integer.

For any positive integer $m$, consider its unique prime factorization $m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}$. Then we have:

\displaystyle \begin{aligned} \phi(m)&=\phi(p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}) \\&=\phi(p_1^{e_1}) \times \phi(p_2^{e_2}) \times \cdots \times \phi(p_t^{e_t}) \\&=p_1^{e_1-1} \cdot (p_1-1) \times p_2^{e_2-1} \cdot (p_2-1) \times \cdots \times p_t^{e_t-1} \cdot (p_t-1) \\&=p_1^{e_1} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times p_2^{e_2} \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times p_t^{e_t} \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=m \cdot \biggl(1-\frac{1}{p_1}\biggr) \times \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times \cdot \biggl(1-\frac{1}{p_t}\biggr)\end{aligned}

In the above evaluation, this fact is used. For any prime $p$, $\phi(p^n)=p^{n-1} \times (p-1)$ (see see Theorem 2 here). We also use the extended version of Theorem 2: if $m_1,m_2,\cdots,m_t$ are pairwise relatively prime, then

$\phi(m_1 \times m_2 \times \cdots \times m_t)=\phi(m_1) \times \phi(m_2) \times \cdots \times \phi(m_t)$.

The extended result is to extend the product to more than two numbers. It is derived by a simple inductive argument.

____________________________________________________________________________

A formula for the phi function

The above evaluation leads us to the following way to express the phi function. For $m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}$, we have the following:

$\displaystyle \phi(m)=m \ \prod \limits_{p \lvert m} \biggl( 1-\frac{1}{p} \biggr)$

In the above product, the $p$ ranges over all prime divisors of $m$. A quick example: for $33075=3^3 \cdot 5^2 \cdot 7^2$,

\displaystyle \begin{aligned}\phi(33075)&=33075 \times \biggl( 1-\frac{1}{3} \biggr) \times \biggl( 1-\frac{1}{5} \biggr) \times \biggl( 1-\frac{1}{7} \biggr) \\&=33075 \times \frac{2}{3} \times \frac{4}{5} \times \frac{6}{7} \\&=315 \times 2 \times 4 \times 6 \\&=15120 \end{aligned}

One comment. For the above formula to work, we only need to know the prime divisors of the number, not necessarily the powers of the primes. For example, for 33075, we only need to know that the prime divisors are 3, 5 and 7.

____________________________________________________________________________

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

# The primitive root theorem revisited

The primitive root theorem lists out all possible values of $m$ for which primitive roots exist in the modulo $m$ arithmetic. The theorem is proved in this previous post and several blog posts leading to it. In this post, we reorganize the proof and add some additional information. The proof of the primitive root theorem detailed below shows that the list of values of the moduli $m$ is very restrictive and, in addition, that such moduli $m$ are such that there are no extra square root beside 1 and -1. The crux of the argument is a lemma that indicates that most moduli have a third square root of 1 in addition to 1 and -1. The proof is also an opportunity for applying the Chinese remainder theorem (usually abbreviated CRT).

____________________________________________________________________________

The primitive root theorem

In this post, $m$ is a positive integer that serves as the modulus. Given $m$, it is of interest to know all the integers $a$ where $1 \le a and that $a$ and the modulus $m$ are relatively prime. The number of such values of $a$ is denoted by $\phi(m)$ (this is called the phi function). For example, for $m=11$, $\phi(11)=10$. For $m=10$, $\phi(10)=4$ since there are only 4 numbers that are relatively prime to 10, namely 1, 3, 7, and 9.

A positive integer $g$ is said to be a primitive root modulo $m$ if $\phi(m)$ is the least positive integer $x$ such that $g^x \equiv 1 \ (\text{mod} \ m)$. If $g$ is said to be a primitive root modulo $m$, it is necessary that $g$ and the modulus $m$ are relatively prime. This is because of this basic fact: $a$ and the modulus $m$ are relatively prime if and only $a \cdot b \equiv 1 \ (\text{mod} \ m)$ if and only of $a^t \equiv 1 \ (\text{mod} \ m)$ for some integer $t$. The middle condition is saying that $a$ has a multiplicative modulo $m$.

The following lemma is alluded to at the beginning. The idea will used through the proof of the primitive root theorem. So it is extracted as a lemma to make the argument easier to follow.

Lemma 1
Let $c$ and $d$ be integers such that $c>2$ and $d>2$ and such that $c$ and $d$ are relatively prime. Let $m=c \cdot d$. Then there exist $x_0$ such that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$ and such that $x_0^2 \equiv 1 \ (\text{mod} \ m)$, i.e. $x_0$ is a third square root of 1 modulo $m$ that is neither 1 nor -1.

Proof
Consider the two equations $x \equiv 1 \ (\text{mod} \ c)$ and $x \equiv -1 \ (\text{mod} \ d)$. By the Chinese remainder theorem, there is a solution $x_0$ to this system of equations. We have $x_0^2 \equiv 1 \ (\text{mod} \ c)$ and $x_0^2 \equiv 1 \ (\text{mod} \ d)$. By the Chinese remainder theorem again, $x_0^2 \equiv 1 \ (\text{mod} \ m)$. There are three possibilities for $x_0$, 1, -1 or another value. If $x_0 \equiv 1 \ (\text{mod} \ m)$, then $1 \equiv -1 \ (\text{mod} \ d)$, which means $d \lvert 2$, contradicting that $d>2$. Similarly, $x_0 \equiv -1 \ (\text{mod} \ m)$ would lead to $c \lvert 2$, which contradicts $c>2$. The only possibility is that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$. $\square$

The proof of Lemma 1 makes use of CRT twice. Lemma 1 will be used several times in the proof of $2 \longrightarrow 3$ in the primitive root theorem.

The Primitive Root Theorem
Let $m$ be a positive integer. Then the following conditions are equivalent:

1. There exists a primitive root modulo $m$.
2. The equation $x^2 \equiv 1 \ (\text{mod} \ m)$ has no solution outside of $\pm 1$ modulo $m$. In other words, the only square roots of 1 modulo $m$ are $\pm 1$.
3. The only possibilities for $m$ are:
• $m=2$,
• $m=4$,
• $m$ is the power of an odd prime,
• $m$ is twice the power of an odd prime.

Proof
$1 \longrightarrow 2$
Suppose that $g$ is a primitive root modulo $m$. Suppose that condition 2 does not hold. As a result, there exists some positive integer $a \not \equiv \pm 1 \ (\text{mod} \ m)$ such that $a^2 \equiv 1 \ (\text{mod} \ m)$. Since $g$ is a primitive root modulo $m$, $a \equiv g^h \ (\text{mod} \ m)$ for some integer integer $h$ with $1 \le h < \phi(m)$ (see Theorem 5 here). If $h = \phi(m)$, then $a \equiv 1 \ (\text{mod} \ m)$. Thus $1 \le h < \phi(m)$.

Furthermore, $a^2 \equiv g^{2h} \equiv 1 \ (\text{mod} \ m)$. We have $\phi(m) \le 2h$, since $\phi(m)$ is the least power $x$ such that $g^x$ is congruent to 1 modulo $m$. Since $g^{2h}=g^{\phi(m)} g^{2h-\phi(m)}$, $g^{2h} \equiv g^{2h-\phi(m)} \equiv 1 \ (\text{mod} \ m)$. We have $\phi(m) \le 2h-\phi(m)$ since $\phi(m)$ is the least power $x$ such that $g^x$ is congruent to 1 modulo $m$. The last inequality leads to $\phi(m) \le h$, contradicting the earlier observation of $h < \phi(m)$. Thus condition 2 must holds if condition 1 is true.

$2 \longrightarrow 3$
We show that for any $m$ outside of the four possibilities listed in condition 3, condition 2 does not hold. This means that if condition 2 holds for $m$, $m$ must be one of the four possibilities. We consider the cases of $m$ even and $m$ odd separately.

Case 1. The modulus $m$ is odd. Since $m$ is not the power of one single odd prime, it must be the product of two or more powers of odd primes. Let $m=c \cdot d$ where $c$ a power of an odd prime and $d$ is the product of one ore more powers of odd primes. It is clear that $c$ and $d$ are relatively prime. It is also the case that $c>2$ and $d>2$ since each of them has at least one odd prime factor. By Lemma 1, there exists a square root $x_0$ of 1 such that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$.

For the second case, $m$ is even. We break this up into two cases. One is that $m$ is a power of 2. The other is that $m$ is not a power of 2. In these two cases, the goal is still to show that if $m$ is outside of the four possibilities in condition 3, then condition 2 does not hold.

Case 2a. The modulus $m$ is a power of 2.
Then $m=2^h$ where $h \ge 3$. In this case, we can actually exhibit a square root that is neither 1 nor -1. Define $x_0=2^{h-1}-1$. Since $h \ge 3$, $x_0>1$. Consider the following derivation:

$\displaystyle x_0^2=(2^{h-1}-1)^2=2^{2(h-1)}-2^h+1=2^h (2^{h-2}-1)+1$

The above derivation shows that $x_0^2 \equiv 1 \ (\text{mod} \ m=2^h)$. It is clear that $x_0 \not \equiv \pm 1 \ (\text{mod} \ 2^h)$.

Case 2b. The modulus $m$ is not a power of 2.
Since $m$ is even and $m$ is not a power of 2, it must be that $m=2^k \times q$ where $q$ is odd. Either $q$ is the power of an odd prime or it is not. If $q$ is the power of an odd prime, then $k \ge 2$. If $q$ is not the power of an odd prime (i.e. $q$ is of case 1 above), then $k \ge 1$. To make the argument clear, we consider the two sub cases separately.

Case 2b-1. The modulus $m=2^k \times p^j$ where $k \ge 2$, $j \ge 1$ and $p$ is an odd prime.
Let $c=2^k$ and $d=p^j$. Note that $m=c \cdot d$. By Lemma 1, there exists a square root $x_0$ of 1 modulo $m$ such that $x_0 \not \equiv \pm 1 \ (\text{mod} \ m)$.

Case 2b-2. The modulus $m=2^k \times b$ where $k \ge 1$ and $b$ is an odd integer that is not the power of an odd prime.
Consider the prime factorization of $b$, say $b=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}$ where $t \ge 2$. Let $c=2^k \cdot p_1^{e_1}$ and $d=p_2^{e_2} \cdots p_t^{e_t}$. We can also apply Lemma 1 to obtain a square root of 1 modulo $m=c \cdot d$ that is neither 1 nor -1.

$3 \longrightarrow 1$
It is clear that there are primitive roots modulo both $m=2$ and $m=4$. For the case of power of an odd prime, see this previous post. For the case of twice the power of an odd prime, see this previous post. $\square$

____________________________________________________________________________

Lemma 1 plays a prominent role in the proof of the direction $2 \longrightarrow 3$. Lemma 1 shows that it is easy to find moduli that have a third square root of 1 (other than 1 and -1). As the primitive root theorem shows, having a third square root of 1 is the condition that kills the possibility of having a primitive root. Lemma 1 and the primitive root theorem speak to different sides of the same coin. One tells us that moduli with no primitive roots are easy to find. The other says that only in rare cases do you find moduli that admit primitive roots, namely the moduli that are not product of two factors, each of which is greater than 2, that are relatively prime. The proof of $2 \longrightarrow 3$ may seem tedious (by listing out all cases that satisfy Lemma 1). The key to understanding the proof is through Lemma 1.
$\copyright \ 2015 \text{ by Dan Ma}$