Euler’s phi function, part 1

This is our first post of an introductory discussion on Euler’s phi function. The next post on phi function is here.

___________________________________________________________________________________________________________________

Setting Up the Scene

The starting point of this discussion is the relative primality of two integers. Two positive integers $a$ and $b$ are relatively prime if $1$ is the only common divisor of $a$ and $b$. Note that $a$ and $b$ need not be prime. For example, $a=9$ and $b=14$ are relatively prime, as are $a=9$ and $b=35$. It is clear that $a$ and $b$ are relatively prime if and only if they share no common prime factors. The last point is equivalent to the condition that the greatest common divisor of $a$ and $b$ is $1$. Our notation for greatest common divisor is $\text{GCD}(a,b)$.

If $a$ and $b$ are relatively prime, we also say that $a$ is relatively prime to $b$ or $b$ is relatively prime to $a$. In the remainder of the blog post, $m$ is always a positive integer that is the modulus used for modular arithmetic.

In modular arithmetic where the modulus is $m$, we only need to focus on $m$ distinct numbers, namely the elements in the set $\left\{0,1,2,\cdots,m-1 \right\}$. Any integer is congruent modulo $m$ to exactly one element of this set (the elements of this set are also called the least residues modulo $m$). For convenience, we use the notation $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$.

An even more interesting set is the set of all integers $a$ in $\mathbb{Z}_m$ such that $a$ and the modulus $m$ are relatively prime. To facilitate the discussion, we describe this set as follows:

$(\mathbb{Z}_m)^*=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\}$

When the modulus $m$ is a prime number, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$, the non-zero elements of $\mathbb{Z}_m$. When the modulus is not prime, there are fewer least residues that are relatively prime to the modulus. The following shows $(\mathbb{Z}_m)^*$ for the first several integers.

$(\mathbb{Z}_{2})^*=\left\{1 \right\}$

$(\mathbb{Z}_{3})^*=\left\{1,2 \right\}$

$(\mathbb{Z}_{4})^*=\left\{1,3 \right\}$

$(\mathbb{Z}_{5})^*=\left\{1,2,3,4 \right\}$

$(\mathbb{Z}_{6})^*=\left\{1,5 \right\}$

$(\mathbb{Z}_{7})^*=\left\{1,2,3,4,5,6 \right\}$

$(\mathbb{Z}_{8})^*=\left\{1,3,5,7 \right\}$

$(\mathbb{Z}_{9})^*=\left\{1,2,4,5,7,8 \right\}$

$(\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\}$

$(\mathbb{Z}_{11})^*=\left\{1,2,3,4,5,6,7,8,9,10 \right\}$

The following theorem gives some indication why $(\mathbb{Z}_m)^*$ is an interesting set, which provides alternative characterizations of $(\mathbb{Z}_m)^*$.

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 number $b$ indicated in condition 2 is said to be the multiplicative inverse of $a$. Theorem 1 says that only the least residues that are relatively prime to the modulus have multiplicative inverses. Condition 3 tells us that to have a power congruent to one, which is of interest in many situations, the base must be relatively prime to the modulus.

We need the following lemma to prove Theorem 1.

Lemma 2

If $\text{GCD}(a,m)=1$, then for any positive integer $n$, $a^n$ is also relatively prime to $m$.

Proof of Lemma 2
Suppose $\text{GCD}(a,m)=1$. By the extended Euclidean algorithm, we have the following:

$ax+my=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

for some integers and $x$ and $y$.

We prove by induction on $n$. When $n=1$, lemma is true. Suppose that $a^n$ is relatively prime to $m$ where $n \ge 1$. We show that $a^{n+1}$ is relatively prime to $m$. Multiple both sides of (1) by $a^n$. We have $a^{n+1} x+m (ya^n)=a^n$. Let $d=\text{GCD}(a^{n+1},m)$. Note that $d$ is a divisor of the left-hand side of $a^{n+1} x+m (ya^n)=a^n$. So $d$ is a divisor of $a^n$. Now we know that $d$ is a common divisor of $a^n$ and $m$. Then $d=1$, which means that $a^{n+1}$ is relatively prime to $m$. $\blacksquare$

Proof of Theorem 1

$\bold 3 \bold \Longrightarrow \bold 2$
Suppose that $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$. If $n=1$, then let $b=1$. If $n>1$, then let $b=a^{n-1}$. Either way, there is $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$.

$\bold 2 \bold \Longrightarrow \bold 1$
Suppose there is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$. Then we have

$ab+my=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

for some integer $y$.

Let $d=\text{GCD}(a,m)$. Since $d$ divides both numbers in the left-hand side of (2), $d \ \lvert \ 1$. Then $d=1$.

$\bold 1 \bold \Longrightarrow \bold 3$
Suppose $\text{GCD}(a,m)=1$. Consider the $a^1,a^2,a^3,\cdots$ and then consider their least residues modulo $m$. By Lemma 2, each $a^n$ and $m$ are relatively prime. Hence the least residue of $a^n$ and $m$ are also relatively prime. But there are only finitely many least residues modulo $m$. So there exist positive integers $i the least residues of $a^i$ and $a^j$ are identical.

We have $a^j \equiv a^i \ (\text{mod} \ m)$. Since $a^i$ and $m$ are relatively prime, we can cancel out $a^i$ on both sides. Thus $a^{j-i} \equiv 1 \ (\text{mod} \ m)$. $\blacksquare$

___________________________________________________________________________________________________________________

Euler’s Phi Function

The Euler’s phi function, denoted by $\phi(m)$, is the number of integers $a$ where $0 \le a \le m-1$ such that $a$ and the modulus $m$ are relatively prime. In light of the above discussion, $\phi(m)$ is the number of elements in the set $(\mathbb{Z}_m)^*$. It is also the case that $\phi(m)$ is the number of elements in $\mathbb{Z}_m$ that satisfies any one of the three conditions in Theorem 1.

If the modulus $m$ is a prime number, then $\phi(m)=m-1$. The following shows several values of $\phi(m)$.

\displaystyle \begin{aligned} &\phi(2)=1 \\&\phi(3)=2 \\&\phi(4)=2 \\&\phi(5)=4 \\&\phi(6)=2 \\&\phi(7)=6 \\&\phi(8)=4 \\&\phi(9)=6 \\&\phi(10)=4 \\&\phi(11)=10 \end{aligned}

When the modulus $m$ is a prime number, Fermat’s little theorem tells us that $a^{\phi(m)}=a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any $a \in (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,m-1 \right\}$. This fact is true even when the modulus is not prime if the power is kept as $\phi(m)$. We have the following theorem.

Theorem 3 (Euler’s Theorem)

We have $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is relatively prime to the modulus $m$.

Theorem 3 can also be stated as: $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ for any $a \in (\mathbb{Z}_m)^*$. The proof is amazingly similar to that of Fermat’s little theorem (see the post Proving Fermat’s Little Theorem). We use the following lemma in proving Theorem 3.

Lemma 4

If integers $h$ and $k$ satisfy any condition in Theorem 1, then so does the product $h \cdot k$.

Proof of Lemma 4

Since the 3 conditions in Theorem 1 are equivalent, it does not matter which one we pick. Condition 2 is probably the most convenient. So we show that if $h$ has a multiplicative inverse and $k$ has a multiplicative inverse, then $h \cdot k$ has a multiplicative inverse modulo $m$.

Suppose $h \cdot h_0 \equiv 1 \ (\text{mod} \ m)$ and $k \cdot k_0 \equiv 1 \ (\text{mod} \ m)$ for some integers $h_0$ and $k_0$ in $\mathbb{Z}_m$. We multiply the two congruences and obtain:

$h \cdot h_0 \cdot k \cdot k_0=(h \cdot k) \cdot (h_0 \cdot k_0) \equiv 1 \ (\text{mod} \ m)$

if $h_0 \cdot k_0$ is in $\mathbb{Z}_m$, then it is the multiplicative inverse of $h \cdot k$. If not, then take the least residue mod $m$. $\blacksquare$

Proof of Theorem 3

Let $a$ be an integer that is relatively prime to the modulus $m$, i.e., $\text{GCD}(a,m)=1$. Let $\left\{t_1,t_2,t_3,\cdots,t_{\phi(m)} \right\}$ enumerate the $\phi(m)$ many elements of $(\mathbb{Z}_m)^*$. Multiply these elements by $a$ and we have the following set:

$A=\left\{a \cdot t_1,a \cdot t_2,a \cdot t_3,\cdots,a \cdot t_{\phi(m)} \right\}$

Consider the least residues modulo $m$ of the members of the set $A$. We have:

$B=\left\{b_1,b_2,b_3,\cdots,b_{\phi(m)} \right\}$

Note that for each $b_j \in B$, $b_j \in \mathbb{Z}_m$ and $b_j \equiv a \cdot t_j \ (\text{mod} \ m)$. We have two claims.

• The numbers $b_i$ and $b_j$ are distinct whenever $i \ne j$.
• Each $b_j$ is relatively prime to the modulus $m$, i.e., $b_j \in (\mathbb{Z}_m)^*$ for each $j$.

The first claims tells us that the set $B$ has $\phi(m)$ many distinct elements. The second claims tells us that the set $B$ is a subset of $(\mathbb{Z}_m)^*=\left\{t_1,t_2,t_3,\cdots,t_{\phi(m)} \right\}$. Since the subset $B$ has $\phi(m)$ many distinct elements and $(\mathbb{Z}_m)^*$ has $\phi(m)$ many distinct elements, they must equal. So we have $B=(\mathbb{Z}_m)^*$. With this information, we have the following congruence equation.

$\displaystyle at_1 \cdot a t_2 \cdot a t_3 \cdots a t_{\phi(m)} \equiv t_1 \cdot t_2 \cdot t_3 \cdots t_{\phi(m)} \ (\text{mod} \ m)$

Because each $t_j$ is relatively prime to the modulus, we can cancel out all $t_j$ and obtain:

$\displaystyle a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$

So the theorem hinges on the two claims listed above. We now prove them one by one. To show the first claim, suppose $b_i=b_j$. Then $a \cdot t_i \equiv a \cdot t_j \ (\text{mod} \ m)$. We can cancel out $a$ on both sides since $a$ is relatively prime to $m$. We have $t_i \equiv t_j \ (\text{mod} \ m)$. Since both $t_i$ and $t_j$ are least residues mod $m$, for them to be congruent to each other, the only possibility is $t_i=t_j$. Thus $i=j$. The contrapositive of what we just show is that if $i \ne j$, then $b_i \ne b_j$. So the numbers $b_j$ are all distinct.

To show the second claim, note that $b_j \equiv a \cdot t_j \ (\text{mod} \ m)$. Both $a$ and $t_j$ are relatively prime to $m$. So by Lemma 4, $a \cdot t_j$ is relatively prime to $m$. Hence $b_j$ is relatively prime to the modulus $m$. $\blacksquare$

___________________________________________________________________________________________________________________

The setting for the phi function deserves some comments. The sets $\mathbb{Z}_m$ and $(\mathbb{Z}_m)^*$ defined above can be considered as algebraic objects.

The set $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$ along with addition and multiplication modulo $m$ is a ring. Thus $\mathbb{Z}_m$ is often called the ring of integers modulo $m$.

Based on Theorem 1 and Lemma 4, the set $(\mathbb{Z}_m)^*$ with the multiplication modulo $m$ is a group, i.e., it is a set with a binary operation called multiplication such that every element has an inverse.

Let the modulus $m$ is a prime number. As indicated above, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$. An interesting angle is that $\mathbb{Z}_m$ can be considered a commutative ring in which every non-zero element has a multiplicative inverse, i.e., $\mathbb{Z}_m$ is a field (in fact a finite field).

Though we do not focus too much on the algebraic side of things in this blog, $\mathbb{Z}_m$, as a field, plays an important role in number theory and has applications in cryptography.

___________________________________________________________________________________________________________________

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