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.

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search