Number Theory and Modular ArithmeticDate: 01/27/2006 at 15:55:05 From: ali Subject: number theory Suppose the order of an element mod(p) = n. Is it true that the order of this element mod(p^k) = n * p^{k-1}, where p is odd prime and k > 1? If yes, how would I prove that? Date: 01/28/2006 at 14:56:43 From: Doctor Vogler Subject: Re: number theory Hi Ali, Thanks for writing to Dr. Math. That's a very good question. The statement that you made is almost true, but it is not quite true. For example, 3 has order 10 mod 11, but it also has order 10 mod 121. Indeed, you could just take m = 1 + s * p^n, and then m has order 1 mod p, and order 1 mod p^n. This provides a counterexample to the conjecture, albeit a rather cheap one. Nevertheless, it illustrates the need for care in stating the theorem. You might be tempted to require m < p, but this is rather an artificial requirement, since it has nothing to do with modular arithmetic. In any case, that's why I chose the example with m = 3 and p = 11. So here is a better idea (although still not quite true): Let k be the largest integer with p^k divides m^n - 1. Then the order of m mod p^i is n if i <= k, and it is n*p^(i-k) if i >= k. This is better, but you can still find a counterexample. Try m=3 and p=2. And yet we can *almost* prove the above theorem. So let's look at what we can get. Lemma 1: If the order of m mod p^i is N, then the order of m mod p^(i+1) is either N or pN. Proof: If we let M = m^N, (which is congruent to 1 mod p^i), then m^(pN) - 1 = M^p - 1 = (M - 1)(M^(p-1) + ... + M + 1). The first factor, M - 1, is divisible by p^i, and each term M^j in the second factor is congruent to 1 mod p^i. There are p such terms, so the sum is congruent to p mod p^i. That means that the product is divisible by p^(i+1), and therefore the order of m mod p^(i+1) divides the number pN. But if p^(i+1) divides m^k, then so does p^i, which means that the order (N) of m mod p^i must divide the order of m mod p^(i+1). The only choices are N and pN. But we can get even more from this: If the number i is at least 2, then that means that the second factor is divisible by p and *not* by p^2, which means that we can prove Lemma 2: If n^(pk) = 1 mod p^(i+1), and n^k = 1 mod p^2, then n^k = 1 mod p^i. Proof: n^(pk) - 1 = (n^k - 1)*(n^((p-1)k) + ... + n^k + 1) is divisible by p^(i+1), and the second factor (the sum) is divisible by p but not by p^2. That means that the first factor must be divisible by p^i. So now we'd like to be able to put all of this together. The idea is that we need to know the order of m mod p, and the order of m mod p^2, and we need to know the smallest power of p (past 2) where the order of m mod p^i changes. So we have Theorem: Given a prime number p, and an integer m not divisible by p, of order n mod p, let k be the largest integer with p^k divides m^n - 1. (By the definition of n, k >= 1.) If k >= 2, then the order of m mod p^i is n when i <= k, and it is n*p^(i-k) when i >= k. If k = 1, then the order of m mod p^2 is pn, and let k' be the largest integer with p^k' divides m^(pn) - 1. Then k' >= 2, and the order of m mod p^i is pn when 1 < i <= k', and it is n*p^(i+1-k') when i >= k'. Proof: In the first case, where k >= 2, the order for i <= k is easily seen to be n (by the definition of k). For i = k + 1, we know that the order is either n or pn by lemma 1, but it can't be n or else k would have been larger. So the order of m mod p^(k+1) is pn. For i > k, we prove by induction on i, with the initial case i = k + 1 already established. Consider what the order of m mod p^(i+1) could be. It must be divisible by pn, so call it pns. Since m^n = 1 mod p^2, so too m^(ns) = 1 mod p^2, and so lemma 2 tells us that m^(ns) = 1 mod p^i. That means that the order of m mod p^i must divide ns, and since the order of m mod p^(i+1) is pns, that means that the order of m mod p^i must be ns. So you multiply by p at each step. In the second case, where k = 1, the order of m mod p^2 is pn by lemma 1, and the order for 1 < i <= k' is easily seen to be pn (by the definition of k'). The rest of the argument is much like that of the above paragraph, so I won't repeat it all. In conclusion, if you look at the order of m mod p, mod p^2, mod p^3, mod p^4, and so on, there are two things that could happen. Case 1: You could start with order n, stay at n for possibly several steps, and then start multiplying by p at every step, as in n, n, n, n, n, n, np, np^2, np^3, np^4, np^5, .... Case 2: Or you could start with order n, then have order pn, and then stay at pn for possibly several steps, before multiplying by p at every step, as in n, np, np, np, np, np^2, np^3, np^4, np^5, .... Of course, the most common thing that happens is that you don't stay for more than one step: n, np, np^2, np^3, np^4, np^5, .... So you might ask yourself if there are only a few cases where you stay for longer. It turns out that it is easy to construct examples where you stay longer in the first case. Pick any prime p, and choose m = a mod p, and find the order n of a mod p. Then if you write m = a + b*p + c*p^2 + d*p^3 + ..., and you multiply out m^n = a^n + n*a^(n-1)*b*p (mod p^2), you can solve for what b has to be in order to get k >= 2. Then you can multiply out m^n mod p^3 and solve for what c has to be in order to get k >= 3, and so on. Staying for several steps in the second case is harder, as you'll see if you try to apply the above method to the second case. You can choose a prime p, and a residue a (mod p), and then compute the order n of a mod p. Then you solve the above equation to find out what b should *not* be, and then you multiply out m^(pn) = a^(pn) + pn*a^(pn-1)*b*p + (1/2)pn(pn-1)*a^(pn-2)*b^2*p^2 (mod p^3) and you solve this for b to see what it *should* be. It turns out that if p is an odd prime, then the last term is 0 mod p^3, and then those two values will always be the same! That means that case 2 can only happen when p = 2. So we can state this in a simpler theorem by excluding the case p = 2: Theorem: Given an odd prime p, and an integer m not divisible by p, of order n mod p, let k be the largest integer with p^k divides m^n - 1, and then the order of m mod p^i is n when i <= k, and it is n*p^(i-k) when i >= k. In the special case p = 2, however, you can have both cases happen. In the case p = 2, if m is not divisible by p (m is odd), then it must have order 1 mod 2. If it is, in fact, 1 mod 4, then we get k >= 2, and we have case 1, with m = 1 + s*2^k for some odd number s. The other possibility is that it is 3 mod 4, and then it has order 2 mod 4, and we compute k', the number of powers of 2 that divide m^2 - 1, which must be at least 3. It turns out that, in this case, m = -1 + s*2^(k'-1) for some odd number s. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 01/30/2006 at 15:21:13 From: ali Subject: Thank you (number theory) Hello Doctor Vogler, Thank you very much for helping me with my question. Your answer was very helpful. I am really happy to find someone like you to deal with! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/