Fermat's Little Theorem and Prime NumbersDate: 09/28/98 at 13:41:06 From: Dan Levitt Subject: Fermat's Little Theorem Dear Dr. Math, Greetings from NYC. I hope you can help me. Please explain how to use Fermat's Little Theorem to test whether a number is prime. Thank you, Dan Date: 09/28/98 at 17:02:31 From: Doctor Rob Subject: Re: Fermat's Little Theorem You can't, but you can test to see if a number is composite! If you think that this is paradoxical, read on. Fermat's Little Theorem says that if n is a prime number, and (a,n) = 1, then a^(n-1) = 1 (mod n). Take the number n that you wish to test. Pick any a you like with 1 < a < n, and compute d = (a,n). If d > 1, n is composite (you have just found a factor, namely d). If d = 1, continue by computing r = a^(n-1) (mod n), with 0 <= r < n. If n is prime, then by Fermat's Little Theorem, r = 1. Thus if r > 1, n cannot be prime, and must be composite. Unfortunately, there are composite numbers n and bases a for which d = 1 and r = 1, such as n = 2047 = 23*89 and a = 2. This means that when r = 1, we cannot say whether or not n is prime, but when r > 1, n is definitely composite. Of course we can repeat this test with different a's. If all of the a's we try give r = 1, we may feel that our inability to prove n composite gives some weight to the allegation that n is prime, but we still do not have a proof. In fact, there are numbers called Carmichael numbers, the smallest of which is n = 561 = 3*11*17, such that whenever d = 1, you will have r = 1, too. There are infinitely many of these, although they are not common, so unless you try all a's up to n^(1/3), you will not be sure by using this kind of test that your n is not a Carmichael number instead of a prime. That is why you cannot use Fermat's Little Theorem to prove a number prime, but you may be able to use it to prove a number composite. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 09/28/98 at 19:21:57 From: Levitt, Dan U Subject: Re: Fermat's Little Theorem Thank you for responding so quickly. If I take: a = 2 n = 7 What is d? 2^6 = 64 After this point I am stuck. How do I proceed further? Please help. Thank You. Dan Date: 09/29/98 at 09:08:33 From: Doctor Rob Subject: Re: Fermat's Little Theorem d is the GCD (Greatest Common Divisor) of 2 and 7, which is 1. You can compute it by using the Euclidean Algorithm: divide the larger number by the smaller, with remainder. If the remainder is zero, stop. If not, replace the larger number by the remainder, and repeat. The last nonzero remainder is the GCD: 7 = 3*2 + 1 2 = 2*1 + 0 The last nonzero remainder is d = 1, the GCD of 64 and 9. Then 2^6 = 64 = 1 (mod 7), so r = 1. Thus you have failed to prove 7 composite. Good thing, since 7 is prime! The notation (a,n) = d means that the GCD of a and n is d. That's a notation used in number theory (and probably nowhere else) which can be confusing. r is the remainder when you divide a^(n-1) by n. Another example: n = 299, a = 3. d = (200,3) = 1, so we compute r = 3^298 (mod 299): 3^8 = (3^4)^2 = 81^2 = 6561 = 282 (mod 299) 3^9 = 3*3^8 = 3*282 = 846 = 248 (mod 299) 3^18 = (3^9)^2 = 248^2 = 209 (mod 299) 3^36 = (3^18)^2 = 209^2 = 27 (mod 299) 3^37 = 3*3^36 = 3*27 = 81 (mod 299) 3^74 = (3^37)^2 = 81^2 = 282 (mod 299) 3^148 = (3^74)^2 = 282^2 = 289 (mod 299) 3^149 = 3*3^148 = 3*289 = 269 (mod 299) 3^298 = (3^148)^2 = 269^2 = 3 (mod 299) Thus r = 3 > 1, so 299 is composite. Notice that this says nothing about what the factors are. You can, however, notice that 3^33 = 1 (mod 299) (because 3^36 = 27 = 3^3 (mod 299)) so that the order of 3 (mod 299) is 33, so the order of 3 (mod p) divides 33 for every prime divisor p of 299. This can be used to reduce the search to a short one, and the factors turn out to be 13 and 23. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/