Determining Primes by Their Square RootsDate: 06/13/2001 at 22:55:48 From: Paul Curtis jr. Subject: Determining primes by their square roots To whom it may concern, I have a bit of a math problem. It has to do with determining if a very large number is a prime. One method entails dividing the number by every smaller prime number. If any divide into it, it's not a prime. This would be a big job if the number was something like 400 digits long. Another way I read about was to take the square root of the number and test all the primes less than its square root. The explanation went like this: "When a number is divided by another number that is greater than its square root, the result is a number smaller than the square root. For example, the square root of 36 is 6. Dividing 36 by 2, a smaller number than 6, gives 18, a number that is larger than the square root. To prove that 37 is prime it is only necessary to divide it by primes less than 6, since if it had a prime factor greater than 6, it would have to have one less than 6 as well." I understand the explanation, up to the last sentence. I fail to see the underlying logic. Why if a prime factor exists below the square does one have to exist above the square too? The number 40 can be divided by the prime 2, a number below its square root, but no other primes can do this above its square root. Have I missed something? What's the logic here? Thanks, Paul Curtis Date: 06/14/2001 at 08:39:01 From: Doctor Rick Subject: Re: Determining primes by their square roots Hi, Paul. You have the statement backward. It says that if a prime factor exists that is GREATER than the square root of the number, then there must be one LESS than the square root - not that if a prime factor exists that is LESS than the square root, there must be one GREATER. (Your example shows that the latter is not true.) Consider the number N = 174, which has a prime factor (M = 29) that is greater than the square root of N (13.2). Since M is a factor of N, we know that N/M = 6 is also a factor of N. We know also that M > sqrt(N) 1/M < 1/sqrt(N) N/M < N/sqrt(N) N/M < sqrt(N) so we know that N has a factor less than the square root of N. This factor, N/M, might be a prime or a composite (in this example, it is composite, 6 = 2*3). If it is composite, however, we know that it has a prime factor that is less than N/M, and therefore less than the square root of N. I have just proved that, if a prime factor exists that is greater than the square root of the number, then there must be one less than the square root of N. Why is this useful in finding primes (as opposed to the turned-around version)? We use proof by contradiction. We are seeking to find out whether N is prime. We have tested all primes less than the square root of N, and found that none is a factor of N. We can stop here, because we know there can be no prime factor of N that is greater than the square root of N. Why? Because, if there were, then there would also be a prime factor less than the square root of N, and we have already found out that there is none. In my example, N = 174, we plan to test all primes up to 13 (2, 3, 5, 7, 11, and 13). When we test for 2 and find that it divides 174, we are done: 174 is not a prime. In the text example, N = 37, we test all primes up to 5 (2, 3, and 5) and find that none divides 37. Therefore we know that 37 is prime without testing any larger primes. If 37 were divisible by a larger prime M, then 37/M would be a factor of 37, and 37/M would have to be a product of the primes we have already tested. Does this explanation help you make sense of what you have read? - Doctor Rick, The Math Forum http://mathforum.org/dr.math/ Date: 06/14/2001 at 08:58:05 From: Doctor Peterson Subject: Re: Determining primes by their square roots Hi, Paul. You reversed the situation when you restated it! The claim is that if 40 had a prime factor GREATER than its square root, it would have one smaller than that as well; you've shown that it has one smaller but none larger. In math it's extremely important to get the order right. The idea is that if N has a prime factor p, then N/p is also a factor. If p > sqrt(N), then N/p < sqrt(N). Now, this may not be prime; but since its factors are no larger than it is, there must be SOME prime factor of N/p (and therefore of N) less than sqrt(N). Can you see why this reasoning doesn't support a statement that if N has a prime factor less then sqrt(N), it must have one greater? - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ Date: 06/15/2001 at 09:00:29 From: Monica Curtis Subject: Re: Determining primes by their square roots Dear Doctor Rick, Thanks for your detailed answer to my query. It did the trick. Paul |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/