Prime Numbers: Checking for a Prime (Part 1)

Last time we looked at how to efficiently make a list of prime numbers. But if you want to check a single large number to see if it is a prime, you don’t want to have to make a list of all primes up to that number. That’s today’s subject, where we’ll start with Trial Division method, useful only for small numbers, and move on to the Fermat test. Next week, we’ll look at some of the more powerful methods.

Try dividing – but by what?

First, consider this 1995 question, which takes us back to some issues we dealt with last time in the broader context:

Finding Prime Numbers

I am writing to you about a question I have about prime numbers.  I know that by definition a prime number is a number that will not divide evenly into any number except for 1 and itself.  I am currently working on a computer program in Turbo Pascal that finds prime numbers.  I am doing this by dividing the number by every integer between 1 and itself-1.  I would like to know if I would get the same exact answers if I were to test the numbers only between 2 and the square root of the number?  

For example if I was checking the number 100 (obviously 100 is composite, but I am just using it for simplicity), I would check every number between 2 and 10, inclusive, instead of checking every number starting at 2 and ending with 99.  Would I get the same answer? 

This has been suggested to me by my math teacher but I am not quite sure what he was saying and I can't ask him now because unfortunately he is in the hospital recovering from open-heart surgery.

Joe meant to say that a prime number is one that can’t be divided evenly by any number except for 1 and itself.

Doctor Eric answered with a brief explanation of the square root idea (which we saw from a different perspective last time, and will see explained more fully below), and also that we can use only primes:

Your teacher was right.  In fact, there's an even more specific set of numbers that you can use, but let's first figure out what he meant.  Why stop at the square root?  Do you see how the square root kind of forms a middle point for divisors of the number?  To get the desired number, you'd have to multiply one number smaller than its square root, and one bigger.  So to test numbers above the square root would be redundant!

    Now, what's even more interesting is that you don't even need to check every integer between 2 and the square root of the number.  I propose that it suffices to only check PRIME numbers between 2 and the square root.  Can you figure out why?  As far as the programming goes, this would involve somehow keeping track of the primes that you've found so far, and then only dividing your next test number by those in this list that are smaller than the square root of the number.

So the best version of this Trial Division Test is to list all the primes from 2 to the square root of our number, and do the divisions. Let’s see, for example, whether 197 is prime.

Its square root is a little bigger than 14. (You can see this with a calculator, or if you happen to know that \(15^2=225\), which is larger than 197.) So we list the primes less than 15, namely 2, 3, 5, 7, 11, 13.

Now we divide:

• \(197\div2=98.5\), not an integer, so we continue.
• \(197\div3=65.6\dots\), not an integer, so we continue.
• \(197\div5=39.4\), not an integer, so we continue.
• \(197\div7=28.1\dots\), not an integer, so we continue.
• \(197\div11=17.9\dots\), not an integer, so we continue.
• \(197\div13=15.1\dots\), not an integer, so it’s prime.

How about 187?

• \(187\div2=93.5\), not an integer, so we continue.
• \(187\div3=62.3\dots\), not an integer, so we continue.
• \(187\div5=37.4\), not an integer, so we continue.
• \(187\div7=26.7\dots\), not an integer, so we continue.
• \(187\div11=17\) exactly, so it’s composite. (namely, \(187=11\times17\))

At several points we didn’t really have to divide, because we know, for example, that a number ending in an odd digit isn’t divisible by 2, and one not ending in 0 or 5 is not divisible by 5. These divisibility tests can save time; but only for certain small divisors. In general, you’d have to divide.

Of course, this method requires already having a list of primes up to some point; for instance, in order to test any number less than 10,000, we would need to know all the primes less than 100. For many purposes, that will be reasonable; but not for really big numbers.

Why stop at the square root?

Paul in 2001 wanted a fuller explanation for that part about the square root:

Determining Primes by Their Square Roots

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?

The teacher’s example of 36 involves a smaller prime, 2, implying a larger divisor, 18 – but that isn’t prime. Paul’s example of 40 points out that in this case there is no prime divisor greater than the square root. The explanation is a little more subtle than the teacher said.

Doctor Rick answered:

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.)

It’s easy to misread (or miswrite) this sort of logic!

A little algebra will start to clear things up:

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.

In the example with \(N=174\), the other factor, \(174\div29=6\), is less than \(\sqrt{174}\approx13.2\); that is not itself a prime, but any prime factor of it will also be less than \(\sqrt{N}\). Not all numbers will have a factor greater than the square root; but if they do, there will also be a factor (and therefore a prime factor) less than the square root.

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.

The proof by contradiction supposes that there is a prime factor that we haven’t tried yet (that is, one greater than the square root), and show that that is impossible, because we would have to have found a prime factor smaller than the root.

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?

It did.

What about really big numbers?

A 2004 question raises the same issues:

Determining If a Number is Prime

Is there a formula for finding if a number is prime?  I've written a program that will tell you if a number is prime, but it is slow for larger numbers because it checks all numbers between 1 and the number to see if they are factors of the larger number.  As you can see, checking a number in the billions would result in billions of divisions, which takes time.

I've tried looking online, but haven't been able to find anything.

He could use the advice given above, if his numbers were only, say, in the millions; but for really big numbers, more would be needed.

Doctor Vogler answered:

Hi Daryl,

Thanks for writing to Dr Math.  There are several "formulas."  They are called "primality tests."  First there are the "pseudoprimality tests" which can quickly tell you if a number is NOT prime, but they can not guarantee that a number IS prime.  The Fermat test is the best-known of these.  The true primality tests are more complicated (which is why you usually start by checking if the number is clearly composite first, with a pseudoprimality test) but they can tell you conclusively whether a number is prime.  In fact, a recent discovery was a "polynomial-time deterministic primality test" which means that it is "fast" by a particular technical definition of "fast."  Other non-deterministic algorithms are more effective or more efficient, but this one is interesting theory.  For precise descriptions of particular primality tests, search Google for "primality test."  See also the account on MathWorld at

  Primality Test
  http://mathworld.wolfram.com/PrimalityTest.html

That page links to descriptions of several tests, some of which we’ll look at next week.

Now let’s look at the Fermat test.

Introducing the Fermat pseudoprimality test

Here is a similar 1998 question:

Primality Testing

Is there any formula to find if a number is a prime? For example, is there a formula to find out if 1642749328584902 is a prime number?

Matthew

Doctor Wilkinson first pointed out the obvious:

An excellent question! Of course your example is not prime, because it ends in 2 and all numbers that end in 2 are divisible by 2.

There is no simple way to check whether a number is prime, but there are methods that work much better for large numbers than just trying all possible divisors. These methods are too complicated to describe in a short note, but I can give you an idea of how they work.

This nicely demonstrates the role of pseudoprime tests: If we can quickly tell that a number is not prime, we don’t need to bring out the big guns.

What follows is a brief version of the Fermat test, starting with its motivation:

If a number is prime and you take any number that is bigger than one but less than the prime, then it turns out that if you keep multiplying by that number, dividing by the prime and taking the remainder, if you do this one less times than the prime, the result is always 1. For example, 7 is a prime. Start with 3 and call that step 1. Multiply by 3 you get 9. Divide by 7 and take the remainder and you get 2. That's Step 2. Now multiply by 3 and you get 6. Divide by 7 and take the remainder and you still get 6. That's step 3. Continuing:

     step 4:  6 * 3 = 18; divide by 7, remainder is 4
     step 5:  4 * 3 = 12; divide by 7, remainder is 5
     step 6:  5 * 3 = 15; divide by 7, remainder is 1

So after 7 - 1 steps you get 1.

What we are doing is raising 3 to the \((p-1)\)st power, here the 6th, but keeping only remainders with respect to p..

We can write this more easily in terms of modular arithmetic, in which \(a\equiv b\text{ (mod }m\text{)}\) means that \((a-b)\) is a multiple of \(m\), so that the remainder when you divide it by \(m\) is zero. In particular, a number is congruent to (\(\equiv\)) its remainder. The work above becomes $$3^2=3^1\cdot3=3\cdot3=9\equiv2\text{ (mod 7)}\\3^3=3^2\cdot3\equiv2\cdot3=6\equiv6\text{ (mod 7)}\\3^4=3^3\cdot3\equiv6\cdot3=18\equiv4\text{ (mod 7)}\\3^5=3^4\cdot3\equiv4\cdot3=12\equiv5\text{ (mod 7)}\\3^6=3^5\cdot3\equiv5\cdot3=15\equiv1\text{ (mod 7)}$$ That is, $$3^6\equiv1\text{ (mod 7)}$$ This will be true for any prime \(p\) and any smaller number \(a\): $$a^{p-1}\equiv1\text{ (mod }m\text{)}$$ This is called Fermat’s Little Theorem.

Now look at it the other way around. Start with a number and suppose you don't know whether it's prime or not. Take a number between 1 and the number and go through the steps I've described. Suppose you don't get a 1. Then you know the number ISN'T a prime.

For example, if we test \(p=10\) for primality, using \(a=3\) again, we get

$$3^2=3^1\cdot3=3\cdot3=9\equiv9\text{ (mod 10)}\\3^3=3^2\cdot3=9\cdot3=27\equiv7\text{ (mod 10)}\\3^4=3^3\cdot3\equiv7\cdot3=21\equiv1\text{ (mod 10)}\\3^5=3^4\cdot3\equiv1\cdot3=3\equiv3\text{ (mod 10)}\\3^6=3^5\cdot3\equiv3\cdot3=9\equiv9\text{ (mod 10)}\\3^7=3^6\cdot3\equiv9\cdot3=27\equiv7\text{ (mod 7)}\\3^8=3^7\cdot3\equiv7\cdot3=21\equiv1\text{ (mod 10)}\\3^9=3^8\cdot3\equiv1\cdot3=3\equiv3\text{ (mod 10)}$$ That is, $$3^9\equiv3\not\equiv1\text{ (mod 10)}$$ So 10 can’t be prime, because if it were, the result would have been 1. (Yes, we knew that already; this is far more useful for large numbers!)

Unfortunately, if you do end up with a 1, you can't say for sure that the number is a prime. But there are fancier versions of this basic idea that will tell you a number is almost certainly a prime if it passes the test.

Also, in the version I've described you have to do an awful lot of multiplying and dividing to do the test. But it turns out you can do the test much faster than the way I've described.

We’ll see more tests next week. We’ll see how to speed things up right now.

Using the Fermat test for a large number

Another 1998 question demonstrated the full Fermat test:

Prime Number Tests

Is the number 55,409,243 prime?  Also, how can you test to see if a number is prime or not?

Doctor Rob answered, starting again with the simplest such test:

No, 55409243 is not prime.

You ask a very good question about testing for primality.  There are quite a few ways to do that.  They range from the very simple, yet time-consuming, to the very sophisticated and quite fast.

The simplest way is to use Trial Division.  Let N be the number in question to be tested. Divide by all prime numbers less than or equal to sqrt(N). If none go in evenly, then N is prime. In your case, you would divide by all the prime numbers less than 7443.73, of which there are more than 900.

I won’t carry out this test!

Here is a slightly more complicated way. 

 1) Pick any a with 1 < a < N-1.
 2) Find the greatest common divisor d of a and N. 
    If d > 1, then N is composite, and d is a factor.  
    If d = 1, then compute the remainder of a^(N-1) when divided by N.
      If this is not 1, then N is composite.
      If this is 1, you can't tell if N is prime or not.  

Most composite numbers will be revealed to be composite by this method, however. This method is called the Fermat Test.

Let’s apply that to our number, \(N=55,409,242\):

In your case, I picked a = 3, and found that a^(N-1) left a remainder of 4483955 when divided by N, so N cannot be prime. This computation involved 26 squarings of 8-digit numbers, 15 multiplications by 3, and 26 divisions by N. This is slightly less work than 900-odd divisions of N by small primes.

You can’t just calculate \(3^{55,409,242}\) and then divide by 55,409,243; calculators can’t hold the numbers that would be involved. (This number would have something like 26 million decimal digits!) We don’t even want to do all 55,409,242 multiplications using remainders, as we did above. To speed the work, we square repeatedly to get large powers quickly, finding remainders at every step to keep the numbers small. There are several variations of this method; here is one version of the work, in which we repeatedly divide the exponent by 2 while squaring the base (modulo N), and multiply the current “result” by the power of the base if the exponent is odd. Each of the 26 rows after the first represents a squaring (and a division by the modulus), and each of the 15 results shown is a multiplication.

$$\begin{array}{rrr}\text{exponent}&\text{base}&\text{result}\\
55409242&3&1\\
27704621&9&9\\
13852310&81&\\
6926155&6561&59049\\
3463077&43046721&22214947\\
1731538&15197407&\\
865769&50930095&49381973\\
432884&21872735&\\
216442&327634&\\
108221&16334265&6737364\\
54110&19328578&\\
27055&43264463&22944554\\
13527&44210924&37489537\\
6763&38849675&51437798\\
3381&1515241&24542770\\
1690&17895133&\\
845&4492694&36364969\\
422&41974568&\\
211&36342724&50016120\\
105&26976110&21228392\\
52&33128489&\\
26&33942363&\\
13&9662916&48207464\\
6&1738737&\\
3&22647846&26937243\\
1&14529912&4483955\\
0&39781892&{\color{red}{4483955}}\end{array}$$

I used a spreadsheet to do this. Since the final result is not 1, this number can’t be a prime.

And it turns out (thank you, Wolfram Alpha) that \(6997\times7919=55,409,243\).

Next time, we’ll dig a little deeper into this test, and then look at some that are more advanced.