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<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.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

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

  1. Pingback: Counting Fermat witnesses | Exploring Number Theory

  2. Pingback: The Fermat primality test | Mathematical Cryptography

  3. Pingback: Euler’s phi functon is multiplicative | Exploring Number Theory

  4. Pingback: Euler’s phi function is multiplicative | Exploring Number Theory

  5. Pingback: Speeding up modular exponentiation using CRT | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s