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 .

In computing modular arithmetic where the modulus is , the following two sets of integers are of interest.

The first set is a representative set under the arithmetic modulo since every integer is congruent mod to exactly one number in . In many settings, the only results of interest for modulo calculations are values in (also called least residues).

The second set consists of all integers in that are relatively prime to the modulus (as the set is defined). So any integer that is relatively prime to the modulus is congruent to exactly one number in . Furthermore, the set is closed under multiplication modulo . It is also the case that every number in has a multiplicative inverse modulo . If we look for numbers a where , we do not need to look further than the set . We have the following theorem.

**Theorem 1**

Let be an integer in . The following conditions are equivalent.

- .
- There is a such that .
- Some positive power of modulo is , i.e., for some positive integer .

The proof of Theorem 1 is found in Euler’s phi function, part 1.

Euler’s phi function is defined to be the number of elements in the set . In this post, we prove two elementary properties of the function . We have the following two results.

**Theorem 2**

Let be a prime number. Let be a positive integer. Then .

**Theorem 3**

Let and be two positive integers that are relatively prime. Then .

**Example**

Before proving the theorems, we work some examples. Find . We factor into its prime factors.

By Theorem 3, the function is multiplicative among integers that are relatively prime. Now we have . Applying Theorem 2, we have:

**Proof of Theorem 2**

Among the integers , the only ones that are not relatively prime to are multiples of (since is a prime number). There are many multiples of . They are:

Thus among the integers , the number of integers that are relatively prime to must be .

Lemma 4 will be helpful in proving Theorem 3.

**Lemma 4**

If is relatively prime to and is relatively prime to , then is relatively prime to .

**Proof of Lemma 4**

Since is relatively prime to , their greatest common divisor is one. Using the extended Euclidean algorithm, for some integers and . Since is relatively prime to , for some integers and . Multiplying these two equations, we get:

The above equation means that . This shows that is the multiplicative inverse of modulo . By Theorem 1, is relatively prime to .

**Proof of Theorem 3**

Suppose and are relatively prime. We show that among the integers , there are exactly many numbers that are relatively prime to . To facilitate the argument, we enumerate the integers as in the following matrix.

There are rows and columns in the matrix. The first observation is that if the first number of a row is and if and are not relatively prime, then there is that is a common divisor of and . Then also divides any other number on that row. So if the first number of a row is and if and are not relatively prime, then any number on the row is not relatively prime to , hence is not relatively prime to .

Based on the above observation, to look for numbers that are relatively prime to , we only need to look at rows where the first number is relatively prime to . There are exactly many such rows.

We claim that in each of these rows, there are exactly many numbers that are relatively prime to . It follows that there are exactly many numbers in the entire matrix that are relatively prime to . Thus the theorem will be established.

To establish the claim in the above paragraph, consider one such row where the first number is relatively prime to . First observe that the numbers in the row are distinct congruent modulo . Suppose that . Cancel out , we have . Since and are relatively prime, we can cancel out and obtain . Since both and are less than , it must be that . So if , .

Based on the observation in the above paragraph, the least residues modulo of the numbers in the row must be the set . This follows from the fact that the numbers in the row are distinct congruent modulo . Hence their least residues must be distinct numbers too.

So in terms of congruence modulo , the row in the matrix is a mirror image of the least resides . There are exactly many least residues that are relatively prime to . Likewise, there are exactly many numbers in the row that are relatively prime to . Furthermore, every number in the row is relatively prime to . By Lemma 4, there are exactly many numbers in the row that are relatively prime to . Thus the above claim is established. It follows that the theorem is established.

___________________________________________________________________________________________________________________

Pingback: Counting Fermat witnesses | Exploring Number Theory

Pingback: More about checking for primitive roots | 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