finding a proof for the Divisor Theorem

Finding a proof for the Divisor Theorem PhL 7.5.13 This all deals with what is now Fact 1 in Appendix E, so it is a done deal. Fact 1: For any integer n not a multiple of prime p, one can find integer m such that n is a divisor of (pm - 1). That is, we can find m such that (pm-1) mod n = 0 which is the same as pm mod n = 1. (E.1) ************************************************* Here is my theorem: Theorem: For any integer n not a multiple of p, you can find m such that n is a divisor of pm - 1. Maple is telling me this is true for any p. Maple suggests that the lowest solution value of m is ≤ n. Here is someone who did exactly what I did on scratch paper at least for the first part: So consider this simpler problem and maybe use it to find the proof. Imagine that we list of the prime numbers in order p1= 1, p2= 2, etc. Then suppose p = pj for some j n = pi for some i ≠ j See if you can find m that works for this simple case of n. We write pm - 1 = Πk pkqk = p1q1p2q2.... Yes p1q1 = 1 but I leave it there. In particular, maybe I can find some pm-1 of this form pm - 1 = p1q1p2q2... pi1....... // there is no factor pjqj since pm - 1 not multiple of p Rewrite this as pjm - 1 = p1q1p2q2... pi1..... // no factor pjqj Claim that we can find m to make this work. So what is it? All I care about is the pi1 factor so I will take take any m such that pjm - 1 has prime factor pi. If these were true, then pjm - 1 = pi N N = some integer with no factor pik . pjm = pi N + 1 In fact ANY solution integer N would be fine by me. For example 3m = 5N + 1 5N = 3m- 1 N = (3m- 1)/5 = integer Consider f(m) = 3m- 1 as a mapping from integers m to integers. How do we know that we will eventually land on an integer that is a multiple of 5 ? Simpler case N = (2m- 1)/3 = integer How do we know that as we increase m, will eventually land on an integer that is a multiple of 3? 21-1 = 1 22-1 = 3 done. Suppose there were no such m. Then we have (2m- 1)/3 ≠ integer for m = 1,2,3....∞ Need to know something about the "landing spots". am = 2m- 1 am+1 = 2m+1- 1 am+1 - am = 2m+1- 1 - (2m- 1) = 2m+1 - 2m = 2m(2-1) = 2m This is the spacing between sequential landing spots. It is not a multiple of 3. Each step up in m causes us to move 2m mod 3 on the grid. For m = 2, 2m mod 3 = 1 so we moved on grid space to the right. So if we were short by 1, this fixes us up. If we were short by 2, then 24 mod 3 = am = 2m- 1 am+r = 2m+r- 1 am+r - am = 2m+r- 1 - (2m- 1) = 2m+r - 2m = 2m(2r-1) Now we have freedom to select r. Suppose at m we are 2 short on the grid. Then we want to select r such that 2m(2r-1) mod 3 = 2 (2m mod 3) (2r-1) = 2 inside GF(3) Then (2r-1) = 2 (2m mod 3)–1 I think that is it! Now try a fancier case: pjm - 1 = pi2 N N = some integer with no factor pik . pjm = pi2 N + 1 In fact ANY solution integer N would be fine by me. For example 3m = 52N + 1 52N = 3m- 1 N = (3m- 1)/52 = integer N = (2m- 1)/32 = integer am+r - am = 2m(2r-1) Suppose for some m I find that Rem[(2m- 1)/32] = 2 Then I want to increase m by r steps such that I move 7 grid spaces to the right. I want 2m(2r-1) mod 9 = 7 Mod(9) is GF(9) which is not a field so all elements don't have inverses. I am back to square zero after an hour or two! Maple shows that when I compute Rem(pm-1,n) for some fixed n and let m increase, the remainder sequences repeatedly through some sequence which always includes 0 but does not generally include all integers. This really can't be so complicated, can it? Fact: If Rem(pm-1,n) = 0, then Rem(pm,n) I first realized this from Little Lemma 2, but it is complete obvious of course. I now think this is true: Theorem: Let p = prime < n. Then there exists integer k such that pk mod n = 1. This then is what makes the Maple repeating sequence. Here is perhaps a lead from wiki on : http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n But what is "the group" ? The notation above means Z / (pk) but seems not too close to me. Well, a red herring. This looks better in wiki http://en.wikipedia.org/wiki/Fermat%27s_little_theorem That Euler's Theorem thing has mod n for any n, which is what I am looking for. I know that gcd(p, n) = 1 if n is my integer which is not a multiple of p which is prime Thus, this Euler theorem would say for a = p pφ(n) mod n = 1 This then gives me the exponent k I have been looking for. Example: n = 4, p = 3, I know that p2 = 9 = 1. And φ(4) = 2, check! This is my baby. Now can I zero in on this little theorem? Wiki has a page just on it! https://en.wikipedia.org/wiki/Euler%27s_theorem Here is a short proof, but it will require work on my part http://philosophyforprogrammers.blogspot.com/2011/07/clever-proof-of-eulers-theorem.html I am optimistic. Now that I have a theorem I can quote, let's finish off what I was doing and only come back here and play if there is time. So: Candidate Material for a new Appendix E (fin 7.6.13) ______________________________________________________________________________ Fact: For any integer n not a multiple of prime p, one can find m such that n is a divisor of pm - 1. Proof: Saying that n is a divisor of pm-1 is the same as saying Rem[(pm-1)/n] = 0. This in turn is the same as saying Rem[pm/n] = 1. If this is not obvious, it follows from Little Lemma 2 *****. Restating one more time, our theorem is equivalent to claiming there exists integer m such that pm mod n = 1. Since we have assumed n is not a multiple of p, and that p is a prime number, we know that GCD(p,n) = 1, so p and n are coprime. After all, p cannot divide n, and nothing smaller than p can divide p but 1. A certain Euler's Theorem claims that for any element of Mod(n) that is coprime to n (such as our p), there exists an integer k such that ak mod n = 1. In our case, that says pk mod n = 1. If we select m = k, then pm mod n = 1 and therefore Rem[pm/n] = 1 and therefore Rem[(pm-1)/n] = 0 and therefore n is a divisor of pm - 1 for this value of m. Our theorem merely claims that such an integer m exists. It happens, according to Euler's Theorem, that the integer m = k is none other than φ(n), Euler's totient function. Integer n can be larger than or smaller than p. Verification: Here we check the above Fact for the first 20 prime numbers and all n < 1000: Fact: If integer D is a divisor of q -1, then GF(q) has at least one element of order D. Proof: We know from (4.21) that [order(αk)] = (q-1)/GCD(k,q-1) where α is any primitive element of GF(q) and k any positive integer. Since D is a divisor of q-1 we can write DM = q-1 where M is the other factor. M then also divides q-1. Setting k = M, [order(αM)] = (q-1)/GCD(M,q-1) But GCD(M,q-1) = M. The reason is that M is a candidate GCD since it divides M and q-1, and no larger integer can divide M, so M is it. Thus we have shown that [order(αM)] = (q-1)/M = D. Thus we have found an element of GF(q), namely αM , which has order D, for any D among the divisors of (q-1). Example: For GF(24) we have q-1 = 15 which has divisors 1,3,5 and 15. If α is a primitive element, then we know α15 = 1 since such an element has order q-1. D 1 3 5 15 M 15 5 3 1 βorder=1 (α15)1= 1 (α5)3= 1 (α3)5= 1 (α1)15= 1 order β 1 3 5 15 Here an element β of GF(q) has been found for each divisor of q-1. For D = 1, β = 1 and 11 = 1 so the identity always has an order to match D = 1. For D = 15 we just get the statement that α is a primitive element α15= 1. It is the interior columns that are important. Fact: If integer D is a divisor of q -1, then GF(q) has at least one minimum polynomial of period D. Proof: From the previous fact, we know that GF(pm) has at least one element α of order D. This element has a minimum polynomial m(x) of the form (x-α)(other factors) . From (5.66) we know that the period of a minimum polynomial is the same as the order of the elements in its conjugate set (here including α), so since α has order D, there exists m(x) of period D. Example: Recall this enumeration (6.21) of the minimum polynomials of GF(24), where we have added the two trivial minimum polynomials shown in (5.24) which are always present : p1(x) = (x - α)(x - α2)(x - α4) (x - α8) = x4 + x + 1 10011 p7(x) = (x - α7)(x - α14)(x - α13)(x - α11) = x4 + x3 + 1 11001 m3(x) = (x - α3)(x - α6)(x - α12)(x - α9) = x4 + x3 + x2 + x + 1 11111 m5(x) = (x - α5)(x - α10) = x2 + x + 1 111 (6.21) m0(x) = (x - α0) = (x-1); mzero = (x - 0) = x; We shall now compute the period of each. First the polynomials are entered: The following procedure scans n downward to find the period of polynomial f(x) : And here are the resulting periods: As claimed in the Fact, there exists a minimum polynomial of period D for each D that divides pm-1. The function x can never divide any xn- 1 so the procedure sets period = ∞. Fact: For any n not a multiple of p, there exists a g(x) which divides xn - 1 and which can therefore be used to construct a cyclic code of length n. Proof: To find a suitable g(x) with coefficients in GF(p), we search through extension fields GF(pm) for m = 1,2,3 ... . We know from Fact X that, for any divisor D of pm- 1, GF(pm) has a minimum polynomial m(x) of period D, so that m(x) divides xD-1. If we can find a value of m such that pm - 1 has a divisor D=n then m(x) divides xn - 1 and this m(x) is a viable g(x). But Fact Y says that we can find m such that n is a divisor of pm -1, namely, m = φ(n). Thus, the field GF(pφ(n)) has a suitable minimum polynomial that can be used for g(x). Corollary: For any n not a multiple of p one can construct a cyclic code of length n whose polynomials have coefficients in GF(p). ______________________________________________________________________________ BUT, for p - 2 I think I showed that there is a g(x) of every degree less than n which divides xn-1, so that seems to by much more general than my result above.