totient

Totient Function PhL 7.7.13 This is development material for Appendix G. I think all matters are resolved. I am looking at this little Euler's Theorem proof http://philosophyforprogrammers.blogspot.com/2011/07/clever-proof-of-eulers-theorem.html 1. Definition of the totient function φ(n). So if you count the number of integers coprime to integer n which are less than n, you get φ(n). First, lets verify this against my little table. coprimes to n φ(n) n = 1 1 1 n = 2 1 1 n=3 1,2 2 n=4 1,3 2 n = 5 1,2,3,4 4 n=6 1,5 2 n = 7 1,2,3,4,5,6 6 For prime number, φ(n) is always n-1. 2. Why is the number of primitive elements of GF(pm) equal to φ(q-1) ? We know that pm-1 = q-1 which has a set of divisors which I know about, but I don't think that is the relevant item. Rather, recall this Fact Fact 6: If β is any element of (α,n,), then the order of β divides n, the order of α. More specifically, we claim that [order of β] = n/GCD(k,n) where β = αk. (4.21) My corollary (stated in App E or F maybe). Let the group be (α,q-1, ) = {GF(q) - 0} so n = q-1. Here α is a primitive element of GF(q). Then the Fact says [order of β] = (q-1)/GCD(k,q-1) where β = αk A corollary to this would be β = αk is a primitive element if GCD(k,q-1) = 1 where k = 1,2...q-2 because αq-1 = 1 Thus, for each k that is coprime to q-1 and is less than q-1, we get a primitive element which is different since all these powers are different. Thus Number of primitive elements = number of integers k that are coprime to q-1 ≡ φ(n) Wow, that was pretty easy. 3. If a and n are coprime, then there exists an inverse of a inside mod n OK, let a be an element of mod(n). We seek an inverse b of a such that ab = 1. OK, this leads to many details: Linear Congruence Theorem, and (a,b) notation for gcd(a,b). One claim is this: ( this is NOT in B&M except when (c,m) = 1. http://math453spring2009.wikidot.com/lecture-7 is where I saw the above. If I can prove this, then this proof of LCT makes sense: and then I can apply this to the inverse idea and then to the group idea G and then get Euler's Theorem. This is definitely another Appendix if I want to do it. I have already made pretty good progress. I am stuck now showing that (a,b) = (a+b,b). Proof supposedly in 3.6 of this book Well, I got the book (parts missing) and found the proof. Here it is July 9, 2013. But found in my Euler's Theorem proof: 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 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. I state the theorem only for a in Gn , but the real theorem says it is valid for all integers a. I have verified this in wiki. Hopefully I just have to modify things a bit. // I just added (1.31a,b) to formally state the mod arithmetic rules, I used these rules many times but never stated them! Suppose b is some arbitrary integer. Then bφ(n) mod n = (bbbb...b) mod n = [ b mod n]φ(n) so now at least we have b inside Zn. If b mod n happens to be in Gn, then we know [ b mod n]φ(n) = 1. But suppose b is NOT in Gn. Then what happens? We know only that b is in Zn. This ring is additively cyclic. Is it cyclic as well? No, it is not a cyclic group because it is not even a group since inverses are missing. Since Zn is not a group, we cannot use any group theory theorem. Consider: This shows that Euler's Theorem is NOT VALID for G6 and a = 4. So OK, wiki and I both have this right. Now look at Fermat. In this case p = 7 say, then *************** 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. Hold this for a moment In the above we may take (α,n,) to be (α,q-1,) where the cyclic group is all of {GF(q) - 0) }, as will be shown in Big Theorem 1 (4.30) below. The order this cyclic group is n = q-1. Thus, Fact 6 specialized to this case says [order of β] = (q-1)/GCD(k,q-1) where β = αk . Here α is an element of GF(q) which has order n=q-1 so that αq-1 = 1. Such an element α is said to be a "primitive element", as described near (4.30) below. We have then proven this Corollary to Fact 6: Corollary. If α is a primitive element of GF(q), and if GCD(k,q-1) = 1, then the element β = αk is also a primitive element. this already appears as (4.32) below! (4.21a)