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.

$\text{GCD}(a,m)=1$ .
There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$ .
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<j$ 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$

___________________________________________________________________________________________________________________

Comments

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.

___________________________________________________________________________________________________________________

5 thoughts on “Euler’s phi function, part 1”

Pingback: Counting Fermat witnesses | Exploring Number Theory
Pingback: The Fermat primality test | Mathematical Cryptography
Pingback: Euler’s phi functon is multiplicative | Exploring Number Theory
Pingback: Euler’s phi function is multiplicative | Exploring Number Theory
Pingback: Speeding up modular exponentiation using CRT | Exploring Number Theory

Exploring Number Theory

A blog on elementary number theory

Euler’s phi function, part 1

5 thoughts on “Euler’s phi function, part 1”

Leave a Reply Cancel reply

Share this:

Like this:

Related

5 thoughts on “Euler’s phi function, part 1”

Leave a Reply Cancel reply