1
Chapter 11: Euler’s Phi Function
Practice HWp. 80 # 1, 2a, 3, 5 (Additional Web Exercises)
In this chapter, we want to look at how to compute efficiently the number , which , is the number of integers between 1 and m that are relatively prime to m. That is,
We would like to have a method of computing when m is larger. The next theorems describe some efficient ways of doing this.
Theorem 1: If p is a prime number, then .
Proof:
█
Example 1: Compute and .
Solution:
█
Theorem 2: If p is a prime number, then .
Proof: The only divisors of are 1 and the powers of p less than k, that is for . Let a be an integer where . If , then must have a factor of , that is . Thus, a number a is not relatively prime ( when . Thus
If , then for some integer k. The multiples of p between 1 and are
,
which is multiples of p. Hence, and thus
.
█
Example 2: Compute .
Solution:
█
We next state and prove a lemma that will be useful in a later result.
Lemma: For integers a, m, and n, if and only if and .
Proof:Assume and suppose . Then and . Hence . This contradicts the fact that . A similar argument can be made if we assume . Thus and
Now assume and and suppose . Then and . By the Fundamental Theorem of Arithmetic, d must have a prime divisor p where . Thus, and . By the prime divisibility property, that says that or . If , since this contradicts the fact that . Similarly, if , since this contradicts the fact that . In either case, we have a contradiction and hence .
█
For example, if a = 5, m = 6, and c = 7, the lemma implies
We next use the previous lemma to prove a fundamental result.
Theorem 3: For two positive integers m and n, if the , then .
Proof: We rearrange the integers between 1 and mn into an array with n rows and m columns.
By Lemma 5,
Consider the column of the array. Each entry in the column when paired with m, has the same greatest common divisor.
Continued on Next Page
That is, if , (This can be seen by calculating both using the first step of the Euclidean Algorithm). Since all elements in each column have the same greatest common divisor, of the columns will have the elements in the array that are relatively prime to m.
Now, consider the columns. We must now show that each of these columns has elements relatively prime to n, thus giving a total of total elements relatively prime to both m and n and hence by the previous lemma. Consider the column
Claim: In modulo n arithmetic, all entries in this column are just a rearrangement of , that is, each entry in the column is in a the same distinct congruence class as one of the integers . For if not, there would exist integers such that
This implies that
Since by the Theorem assumption, , this implies that which is impossible since . Hence, since the column elements and are the same elements with respect to congruence in modulo n arithmetic and there are elements relatively prime to n in list , there are elements in the column
relatively prime to n. Thus there are columns in the array containing the elements relatively prime to n, and in each of these columns entries relatively prime to n. This gives a total of total elements that are relatively prime to both m and n. Since, by the previous lemma, these are the same elements relatively prime to , we have the result
█
Example 3: Compute .
Solution:
█
Theorem 4: If m has the prime factorization , then
.
Proof: We can prove this result using mathematical induction. For the trivial case, that is, if , then using Theorem 13.6 we have
.
Now, assume the result is true if m is a product of r primes. We want to show the result is true if m is a product of r + 1 primes. Suppose . Noting that we have
Hence, by the principle of mathematical induction, the result holds.
█
Corollary 1: If p and q are primes where , then .
Proof:
█
Example 4: Compute .
Solution:
█
Example 5: Compute .
Solution:
█
Example 6: Compute .
Solution:
█
Euler Phi Function with Maple
Note that the numtheory package must be loaded to the home directory using the with statement before the phi command can be used.
> with(numtheory):
Compute .
> phi(35);
Compute .
> phi(360);
Compute .
> phi(1575);
Chinese Remainder Theorem
Theorem 5: Chinese Remainder Theorem. The system of linear congruences
*
where (Moduli are pairwise relatively prime) can be solved for an integer x modulus . Moreover, if y is another solution to these congruences, then .
Proof: Let for .
Then (Proof Exercise). By the Linear Congruence Theorem, there exists an integer where
(Note is the multiplicative inverse of mod
Also, whenever . (Proof Exercise)
Let
Claim that x satisfies every linear congruence. To show, that the jth arbitrary congruence with modulus . Then
Continued on Next Page
To show there are no other incongruent solutions, suppose y is another solution to *. Then for all , . Since , it follows that
Thus, . Since when , then it follows that
Hence, and . This completes the proof.
█
Chinese Remainder Theorem Summary
To solve the system of linear congruences
We compute
where
- each comes from the right had side of the given congruences
- ,
- for ,
- is the multiplicative inverse of mod , that is, solves the congruence
for .
Example 7: Use the Chinese Remainder Theorem to solve the system of congruences
, ,
Solution:
█
Using the Chinese Remainder Theorem in Maple
To solve , ,
> chrem( [2, 4, 6], [3, 5, 19] );