Exploring Fermat's Little TheoremDate: 02/08/2001 at 00:59:12 From: G.Siva Prasad Subject: Modular Arithmetic For two integers, m and n, which are relatively prime, what is the least possible integer e such that this is true? (m^e) mod n = 1 It is true for e = (n-1), from Fermat's Theorem. What are the criteria for existence of another e < (n-1) for which the above equality holds? Date: 02/08/2001 at 02:17:46 From: Doctor Schwa Subject: Re: Modular Arithmetic Hi, First I'd like to point out that it's true for e = n-1 in the case where n is prime, but not necessarily otherwise. In fact checking whether some number to the n-1 = 1 (mod n) is a test sometimes used for primality; if it's not = 1 then you know n is not prime. In answer to your main question, identifying the "primitive roots" mod n (which is to say, the numbers which first return to equal 1 after the maximum possible exponent) is not a simple question. In fact I don't know of any algorithm that's easier than simply exponentiating the number (with the usual shortcuts for exponentiating). - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ Date: 02/08/2001 at 05:07:53 From: Siva Prasad Gummadi [T] Subject: Re: Modular Arithmetic Hello, Thank you for the suggestion. I understand that it is difficult to find such an e. But I am still interested in exploring this more. The main thing which I'd like to point out in your reply is this: m^(n-1) = 1 mod n, for m and n relatively prime, AND 'n' PRIME. I feel that this extra condition on n is not required. Please refer to your Web document under 'Fermat's Little Theorem,' where the proof is given for this. I'll use the symbols used there. a^(p-1) = 1 mod p, for prime p, and for a relatively prime to p Let us get into the proof, step by step, with a p which is not prime. If we can show that the set {[a]mod p,[2a]mod p,...,[a(p-1)]mod p} is nothing but the permutation of the set {1,2,..(p-1)}, then the rest of it follows automatically. For this we choose two numbers m and n (as chosen in the proof) and assume that they are congruent mod p. This implies that p|(m-n)a. Since a is relatively prime to p, 'all' of p must divide (m-n). But since (m-n) < p, it's a contradiction. So the set is a permutation of the original. In the final step, you can always cancel out (p-1)! mod p in the equation (p-1)! mod p = a^(p-1)) mod p * (p-1)! mod p Hence the result. Please let me know your comments on this. Thank you. G.Siva Prasad, MIEL, Bangalore, India Date: 02/08/2001 at 06:16:35 From: Doctor Schwa Subject: Re: Modular Arithmetic The primality condition on n is not REQUIRED, in the sense that there exist SOME n for which m^(n-1) = 1 mod n even though n is not prime. But it's certainly not true for all n. For example, 3^9 = 3 (mod 10). >Please refer to your web document under 'Fermat's Little Theorem,' >where the proof is given for this. I'll use the symbols used there. You'll need to read about "Euler's theorem", which says that in general if a and m are relatively prime, then a^(phi(m)) = 1 (mod m). phi(m) is the number of numbers, 1...m, that are relatively prime to m. So for instance, phi(10) = 4 because of 1, 3, 7, 9. I think I agree with your proof up to this step: >In the final step, you can always cancel out (p-1)! mod p in the >equation > > (p-1)! mod p = a^(p-1)) mod p * (p-1)! mod p Here's the part I disagree with completely. If p = 10, then (p-1)! is divisible by 10, hence equal to 0 mod 10, so you can't divide by it. The reason for Euler's generalization is that he uses just the set of things relatively prime to p. Then, the product of those things is not equal to zero mod p, because they all have inverses. I hope that helps clear things up. - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ Date: 02/08/2001 at 07:13:27 From: Siva Prasad Gummadi [T] Subject: Re: Modular Arithmetic Hi, Thank you for the clarification. In fact, I realized the mistake a few minutes after sending you the mail. Sorry for troubling you. So, I'd like to sum up all by stating this: ------ If a and n are relatively prime, then for the statement a^(n-1) = 1 mod n to be true, the following condition on n is 'sufficient': n is a prime, OR n = k^m, for some integers k and m. ------ I'll try to find the 'necessary' conditions on n in the above statement. I'll mail you in case I make any improvement, or for any other suggestions in my favorite number theory. Hope you don't mind. G.Siva Prasad, MIEL, Bangalore Date: 02/08/2001 at 12:29:10 From: Doctor Schwa Subject: Re: Modular Arithmetic >So, I'd like to sum up all by stating this: >------ >If a and n are relatively prime, then for the statement > > a^(n-1) = 1 mod n > >to be true, the following condition on n is 'sufficient': > > n is a prime, OR > n = k^m, for some integers k and m. >------ I still disagree with this statement. For example, 3^7 = 1 (mod 8) is not true. >I'll try to find the 'necessary' conditions on n in the above >statement. I'll mail you in case I make any improvement, or for any >other suggestions in my favorite number theory. Hope you don't mind. Of course I don't mind! That's why we volunteer here. - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ Date: 02/09/2001 at 04:51:35 From: Siva Prasad Gummadi [T] Subject: Re: Modular Arithmetic Hello, Thank you very much. That was a mistake. I should have verified it before mailing you. But I think this time I got some interesting points: (1) For a^(p-1) = 1 mod p, it is necessary that a and p be relatively prime. Proof: Assume that they are not relatively prime; the statement implies that a^(p-1) - (some integer)*p = 1 So we can take out the common factor, (common factor) * (some integer) = 1, which is obviously wrong. Hence the result. (2) The statement that (p-1)! is not divisible by p is equivalent to saying that p is a prime OR p = 4. Proof: It is obvious for a prime. Let p be other than prime. Let p = m*n. If p is not of the form k^m, then in the (p-1) terms of (p-1)!, all the factors of p occur. So (p-1)! mod p = 0. This narrows down the choice of p to numbers of the form k^m. Let us now assume that (k*m) < k^m. Then in (p-1)! we will have the following terms: (k*1),(k*2),(k*3),...,(k*m) and thus (p-1)! is divisible by p or k^m. So, p must be of the form k^m, with k*m >= k^m. This implies that m >= k^(m-1) or log(m) >= (m-1)log(k) Taking the log base 2, since k>=2, log m >= (m-1) or m >= 2^(m-1) But this is true only for m=1 or m=2. We discard m=1, since it really does not suit the form k^m. So, m = 2. With this, m >= k^(m-1) becomes 2 >= k So, k=2. That means that p = k^m = 4, if it's not a prime. You might already know these results. It's just out of curiosity that I am writing this. Can I say the following? ------ If a and p are relatively prime, then for the statement a^(p-1) = 1 mod p to be true, the following condition on n is 'sufficient': p is a prime, OR p = 4. ------ Or, still better would be: ------ For the statement a^(p-1) = 1 mod p to be true, the following is a necessary condition: a and p are relatively prime. The following are sufficient conditions: p is a prime or p=4. ------ So, the necessary conditions are still unknown. Same with regard to the "least possible exponent" such that a^e = 1 mod p. I'll work on these. Tell me if there are still any bugs in this. G.Siva Prasad, MIEL, Bangalore Date: 02/09/2001 at 19:31:24 From: Doctor Schwa Subject: Re: Modular Arithmetic >(1) For a^(p-1) = 1 mod p, it is necessary that a and p be relatively prime. Indeed, and your proof is absolutely correct. >(2) The statement that (p-1)! is not divisible by p is equivalent to >saying that p is a prime OR p = 4. In number theory, it's customary to use "n" for a general integer, and reserve p for ones known to be prime. So I'd modify your notation a bit, (n-1)! is not divisible by n iff n is prime or n = 4 but I'd certainly agree with the result. >You might already know these results. It's just out of curiosity >that I am writing this. Can I say the following? That's fine! The best way to do math is to discover it for yourself, and then compare it with what other people have done, and then go on for yourself. I'm very impressed by your patience and by your interest in the subject. >------ >If a and p are relatively prime, then for the statement > > a^(p-1) = 1 mod p > >to be true, the following condition on n is 'sufficient': > > p is a prime, OR > p = 4. >------ I don't think so! For instance, let's try p = 4, and a = 3. Your claim then is that 3^3 = 1 (mod 4), but in fact it equals 3. What went wrong? Even if (4-1)! is not divisible by 4, it's still true that you can't divide by it. In other words, we know that 3^3 * (4-1)! = (4-1)! (mod 4) and we want to conclude that 3^3 = 1 (mod 4) but we can't conclude that because dividing by 2 is illegal (mod 4). The first statement says 3 * 2 = 2 (mod 4), which is true, and the second statement (after dividing by 2) would say 3 = 1 (mod 4), which is not true. So it appears that only primes work, because the condition is not that (n-1)! not be divisible by n; the condition is that gcd((n-1)!,n) = 1. I think the second statement has the same bugs: p must be prime (p=4 doesn't work). But I agree that there is still a lot that's unknown. Finding how MANY elements there are such that a^e = 1 (mod p) for any particular e is a problem with a known solution, but finding WHICH ONES have that e is unknown (at least to me). There is a nice tricky bit of math involved in finding out whether there are any elements not equal to 1 such that a^(n-1) = 1 (mod n) when n is not prime. I *think* I know enough to be able to answer this question definitively, but I haven't taken the time to write down and check my idea carefully. My summary of what we have so far would be: If n is prime, a^(n-1) = 1 (mod n) if and only if a is relatively prime to n. If n is not prime, we don't know yet about a^(n-1), but there is a nice fact about a^(certain function of n) = 1 (mod n) for all a relatively prime to n. Do you know what that function is? It's named after Euler, and the answer can be found by searching the Dr. Math archives if you don't want to try to solve the problem yourself. Thanks for the conversation! - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ |
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/