Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Determining Primes by Their Square Roots


Date: 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
    
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/