Appendix G

Appendix G: Totient PhL 7.8.13 Appendix G: GCD, mod n, totient φ(n), Euler Theorem, Fermat's Little Theorem Here we take a brief tour of "number theory" with the goal being to arrive at the endpoints of Euler's Theorem (Fact 11) and Fermat's Little Theorem (Fact 12). More trees in the forest. The entire thread presented here (excluding a few references to items in the main document) is completely self-contained, and each Fact has a proof. In our selected pathway, every Fact in this section is required to get the train to the station. No doubt there are shorter paths, but all these Facts are worth stating and proving. If the GCD and Mod concepts are old hat to you, all these Facts will all be familiar. Euler's Theorem is used in Appendix E to prove (E.1). The final two Facts 13 and 14 (the coda) show how the number of primitive elements and the number of primitive polynomials of a Galois Field are related to the totient function φ defined below in (G.14). _____________________________________________________________________________________ Fact 0: These fundamental modulo arithmetic rules were stated and derived in (1.31b) : (x+y+z + ...) mod n = ( [ x mod n] + [ y mod n] +[ z mod n] + ... ) mod n (x*y*z + ...) mod n = ( [ x mod n]* [ y mod n] * [ z mod n] + ... ) mod n (1.31b) _____________________________________________________________________________________ Fact 1: Let d = GCD(c,m). Then by the meaning of "common divisor" there must exist integers N1 and N2 such that c/d = N1 and m/d = N2. The fact claims that GCD(N1,N2) = 1. (G.1) Proof: Suppose GCD(N1,N2) = K > 1. Then there must exist integers M1 and M2 such that N1/K = M1 => N1 = M1K => c/d = M1K => c/(dK) = M1 N2/K = M2 => N2 = M2K => m/d = M2K => m(dK) = M2 . The equations on the right show that then dK > d is a common divisor of c and m which is a contradiction since d is supposed to be the largest common divisor. QED. _____________________________________________________________________________________ Fact 2: Suppose GCD(N1,N2) = 1 and N1A = N2B. Then N2 divides A and N1 divides B. (G.2) Proof: If N1 = 1 then A = N2B so N2 divides A and of course N1 = 1 divides B. If N2 = 1 then B = N1A so N1 divides B and of course N2 = 1 divides A. If N1>1 and N2> 1 and if N1A = N2B, then N2 divides N1A (quotient B). But if GCD(N1,N2) = 1, N2 cannot divide N1 because if it did then N2 > 1 would be a common divisor of N1 and N2. Thus, if N2 divides N1A then N2 must be dividing A. Similarly, N1 must divide B. _____________________________________________________________________________________ Notation: The notation a = b mod m is a shorthand for a mod m = b mod m, or (a-b) mod m = 0. It means that a and b are congruent mod m. The notation is a little misleading since it seems to say for example 100 = 100 mod 4 = 0 so 100 = 0, but that is not what it means. It means that 100 is congruent with 0 mod 4. A better notation might be a = b (mod m), but that adds clutter. Note then that for a and b integers in Z, there exists an integer I such that a = b mod m a mod m = b mod m (a-b) mod m = 0 (a-b) = I m a = b + I m (G.3) _____________________________________________________________________________________ Fact 3: ca = cb mod m a = b mod (G.4) Proof: Let d ≡ GCD(c,m). As in Fact 1, there exist N1 and N2 such that c = N1d m = N2d => = = N2 = an integer (which is promising!) Proof in the direction: ca = cb mod m => ca = cb + em => c(a-b) = em => N1d(a-b) = em => a-b = = . If we can show that is an integer, then we have shown that a = b mod as claimed. Go back to N1d(a-b) = em => N1(a-b) = e => N1(a-b) = N2 e . Since GCD(N1,N2) = 1 by Fact 1, Fact 2 says that N2 divides (a-b). Now write the last equation as = Since we just showed that N2 divides a-b, we have shown that is an integer, QED. Proof in the direction: If a = b mod N2 then a = b + kN2 and ca = cb + ckN2. But ckN2 = (N1d)k = (N1k)m Thus ca = cb + (N1k)m and so ca = cb mod m. QED. _____________________________________________________________________________________ Corollary 3. If GCD(c,m) = 1 then [ ca = cb mod m a = b mod m ] . (G.5) In this special case of Fact 3, if we see ca = cb, we can divide both sides by c to get a = b mod m. _____________________________________________________________________________________ Fact 4: (Linear Congruence Theorem). If ax = b mod m and GCD(a,m) = 1, there is a unique mod-m solution x. (G.6) Comment: If a = b mod m, then a and b are said to be congruent mod m. The set of integers a which are congruent to b mod n is called a congruence class. The set of such values was called a residue class in our residue class ring discussion of Chap 1 (c), with an example shown in (1.32). In this Fact our equation to be solved is ax = b which is a linear equation and ax is congruent to b mod m, hence the theorem name. History: An equation of two of more variables, like ax2 + by + cy3 + dz = e, in which all coefficients and variables are restricted to be integers, is called a Diophantine equation, named after a Greek algebra guy Diophantus circa 250 BC. An equation like ax + by = c is a linear Diophantine equation. We saw an example of this in (1.43), Bezout's Identity d = x n1 + y n2 where d = GCD(n1,n2) and we want to solve for integers x and y. In our current Fact 4, we have ax = b mod m which is a "linear Diophantine equation mod m". Hilbert's 10th Problem (1900) was to find an algorithm which could determine whether a given Diophantine equation has a solution or not. The work of several people from 1944 to 1970 showed that such an algorithm does not exist for the general case. Proof of Fact 4: We want to solve ax = b mod m for x. Consider the linear Diophantine equation ay - mz = 1 1 = GCD(a,m) variables y,z Since this is the Bezout Identity (1.43), we know there exists an integer solution for y and z. So we have a specific value of y. Multiply by b to get a(by) = b + m(bz) => a(by) = b mod m Thus our solution is x = by. Suppose there were another solution x'. Then ax = b mod m ax' = b mod m => ax = ax' mod m Since GCD(a,m) = 1, Corollary 3 says that x = x' mod m. Thus our solution x = by is the only solution mod m. QED _____________________________________________________________________________________ Corollary 4: Element a of Zm has an inverse if GCD(a,m) = 1. (G.7) Proof: In Fact 4 we showed that in this case ax = b mod m had a unique solution. Setting b = 1 we find that ax = 1 has a unique solution. But that solution is a-1. [ Zm means Mod(m, +, ) ]. _____________________________________________________________________________________ Fact 5: Given a,b > 0, and if x and y exist such that ax+by = 1, then gcd(a,b) = 1. (G.8) Proof: Suppose gcd(a,b) = Q > 1. Then a = QN1 b = QN2 => 1 = ax+by = (QN1)x + (QN2)y = Q (N1x + N2y) => 1/Q = N1x + N2y . But since Q > 1, this says fraction = integer which is a contradiction, so Q = 1. _____________________________________________________________________________________ Fact 6: If gcd(a,m) = 1 and gcd(b,m) = 1, then gcd(ab,m) = 1. (G.9) Proof: From the if conditions we know from Bezout's Identity (1.43) that x,y,x',y' exist such that 1 = ax + my and 1 = bx' + my'. Thus, 1 = (ax + my)( bx' + my') = ab(xx') + m (ybx'+axy'+myy') = ab x" + m y" . From Fact 5, since (ab) x" + m y" = 1 we conclude that gcd(ab,m) = 1. _____________________________________________________________________________________ Fact 7: For any integer I, gcd(a + Im, m) = gcd(a,m). (G.10) Proof: (1) Let s be some common divisor of a and m. Clearly s divides a+Im. Thus, s is a common divisor of the pair a+Im and m. So { common divisors of a and m } { common divisors of a+Im and m } . (*) (2) Let s be some common divisor of a+Im and m. Does s divide a? To find out, consider a+Im = s N1 m = s N2 N1 = = + I = + I N2 => = N1 - I N2 Thus, is an integer so yes, s does divide a. Thus, s is a common divisor of m and a. So { common divisors of a+Im and m } { common divisors of a and m } (**) (3) We conclude from (*) and (**) that the two common divisor sets are the same set, call it Q. Suppose this set is Q = {1, 5, 17}. Then gcd(a + Im, m) = 17 and gcd(a,m) = 17. In general, we find that both gcd(a + Im, m) and gcd(a,m) will be the largest element of Q, so gcd(a + Im, m) = gcd(a,m). QED. _____________________________________________________________________________________ Fact 8: gcd(a mod m, m) = gcd(a,m) (G.11) Proof: We know that a mod m = a + Im for some integer I (I < 0 if a > m). Thus from Fact 7 we have that gcd(a mod m, m) = gcd(a + Im, m) = gcd(a,m). QED _____________________________________________________________________________________ Fact 9: For a,b in Zm (with + and ), gcd(ab, m) = gcd(ab mod m, m) = gcd(ab,m). (G.12) Proof: The meaning of ab is that this product is some element c within Zm which is closed under . The rule for finding this element c is c = ab mod m, so ab = ab mod m. Then the last equality shown follows from Fact 8. _____________________________________________________________________________________ Definition: Integers n and m are coprime (relatively prime) iff GCD(n,m) = 1. (G.13) Definition: The set of integers < n which are coprime with n are called the totatives of n. We shall refer to this set as Gn in what follows. (G.14) Example: The totatives of n = 12 are {1,5,7,11} . Definition: Euler's totient function φ(n) is the number of totatives of n. (G.15) Examples: φ(12) = 4 since the set {1,5,7,11} has four elements. φ(7) = 6 since the set {1,2,3,4,5,6} has 6 elements. φ(p) = p-1 if p is prime Comment: It happens that the sum of the totatives of n is (n/2)φ(n), but we shall not prove it since we don't need it. In our example with n = 12, 1+5+7+11 = 24 and (n/2)φ(n) = 6*φ(12) = 6*4 = 24. Here are the first 100 values of φ(n) in the form _____________________________________________________________________________________ Fact 10: The set Gn of the totatives of n forms an abelian group under within Zn of order φ(n). (G.16) Proof: The properties of a group are shown in (1.1). We know that G is closed under from Fact 6 which reads " if a and b are in Gn, then ab is in Gn ". We know from (1.29) that Zn forms an abelian ring with identity, so any subset of Zn which includes 1 has the commutative, associative, and identity-exists properties for operator . What is missing is the existence of a inverse. When n is a prime p, we showed such an inverse always exists and Zp is then a field GF(p). But for general Zn some inverses do not exist. However, for our set Gn inverses always exist due to Corollary 4 above. Thus Gn is a group of order φ(n). Example: Z8 = {0,1,2,3,4,5,6,7} = Mod(8,+,) G8 = {1,3,5,7} with operation of Z8. Note that φ(8) = 4. 3 3 = 9 mod 8 = 1 G8 3-1 = 1 5 5 = 15 mod 8 = 7 G8 5-1= 7 3 5 = 15 mod 8 = 7 G8 5 7 = 35 mod 8 = 3 G8 3 7 = 21 mod 8 = 3 G8 7 7 = 49 mod 8 = 1 G8 7-1 = 1 Thus, G8 is closed under and all elements have an inverse. _____________________________________________________________________________________ Fact 11: (Euler's Theorem). For any a in Gn, aφ(n) = 1 mod n . (G.17) Proof: Fact (1.9e) says that for any a in group G, an = 1 where n is the order of the group. What that means here is aaa...a = 1 where we have φ(n) factors of a since from Fact 10 the order of Gn is φ(n). The operation is that of Zn of which Gn is a subset. For elements in Zn we know that ab= ab mod n. Thus, aaa...a = aφ(n) mod n if we interpret aφ(n) as aaaa..a (integer multiplication). Thus, we have Euler's Theorem: aaa...a = aφ(n) mod n = 1 or aφ(n) = 1 mod n // see (G.3) This theorem was proved by Euler in 1763. The theorem and the totient function φ(n) play a major role in current day RSA public key cryptography. _____________________________________________________________________________________ Fact 12: (Fermat's Little Theorem). If p is prime and a is any integer, then ap = a mod p. (G.18) Proof: For n = prime p, Gp = {1,2,3, .... p-1} = Zp and φ(p) = p-1. Fact 11 then says ap-1 = 1 mod p for any a in Gp. Since any a in Gp and p are coprime, meaning GCD(a,p) =1, we can apply Corollary 3 and multiply both sides of ap-1 = 1 mod p by a to get ap = a mod p for any a in Gp = Zp. We can then extend the theorem to any integer a using Fact 0 to say, ap mod p = {[a mod p] * [a mod p] ...} mod p = [a mod p]p mod p = 1 where the last equality follows since a mod p lies in Gp. There is no restriction to positive integers, since every negative integer is congruent to a positive integer, such as (-19) mod 7 = (-5) mod 7 = 2 mod 7 = 2. Then [(-19)7 - (-19)] mod 7 = (27 - 2) mod 7 = 126 mod 7 = 0. Also, for a = 0, 0p = 0 = 0 mod p = 0. Comments: This theorem was stated by Fermat in 1640 without proof (as was his custom) and was later proved by Euler in 1736. In the Fermat primality test, if one can find an integer a such that ap-1 mod p ≠ 1, one knows that p is not prime. The converse of the theorem is not true: that ap = a mod p for all a => p is prime. This converse fails for integers known as Carmichael numbers (Fermat pseudoprimes), the smallest of which is 561 (found in 1910 by Carmichael). Here we test 561 = 3*11*17 for a = the first 10,000 integers: There are an infinite number of these pseudoprimes. Fermat's "big" theorem was his Last Theorem which says that the Diophantine equation xn + yn = zn has no solutions for n > 2 and x,y,x > 0. This theorem was conjectured by Fermat in 1637 in a margin note and was first proved by Andrew Wiles in 1995, some 358 years after the conjecture was made. _____________________________________________________________________________________ Fact 13: The number of primitive elements in Galois Field GF(q=pm) is φ(pm-1). (G.19) Proof: First we quote (4.32): Fact 12: A power αk of a known primitive element α of GF(q) is itself a primitive element if and only if GCD(k,q-1) = 1. (4.32) Since powers of α enumerate all of {GF(q) - 0, }, we can just try all powers αk for k = 1 to q-2 and see whether or not the condition GCD(k,q-1) = 1 is valid for that power. If the condition is true, αk is a primitive element. Then the number of primitive elements of GF(q) is the number of integers k < q-1 which are coprime to q-1. But this is exactly the set Gq-1 of totatives of q-1 discussed above, a set we showed has φ(q-1) elements. Thus, the number of primitive elements of GF(q) is just φ(q-1). QED _____________________________________________________________________________________ Fact 14: The number of primitive polynomials in Galois Field GF(pm) is φ(pm -1)/m. (G.20) Proof: We know from (5.15) that a primitive polynomial has coefficients which lie in a conjugate set which contains m elements, all of which are primitive elements. The primitive polynomials for all m elements in such a conjugate set are the same primitive polynomial since they have the same roots of GF(q). Thus, we have to divide the total count of primitive elements by m to get the total number of distinct primitive polynomials for GF(q). QED. _____________________________________________________________________________________