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}

Advertisements

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

  1. Pingback: Counting Fermat witnesses | Exploring Number Theory

  2. Pingback: More about checking for primitive roots | Exploring Number Theory

  3. Pingback: The Fermat primality test | Mathematical Cryptography

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

  5. Pingback: Euler’s phi function is multiplicative | 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