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 bydividing 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 onlybetween 2 and the square rootof 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 teacherbut 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 multiplyone 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 toonly 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 entailsdividing 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 andtest 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 of36is 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 factorgreater than 6, it would have to have oneless than 6as 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 number40can 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 thatif a prime factor exists that is GREATERthan the square root of the number, then there must be one LESS than the square root -notthatif a prime factor exists that is LESSthan 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 isgreater 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 factorless 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 aprime factorthat is less than N/M, and therefore less than the square root of N. I have just proved that,ifa prime factor exists that isgreaterthan the square root of the number,thenthere must be onelessthan 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 useproof 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 knowthere 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, andwe 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, and37/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 PrimeIs 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 becauseit checks all numbers between 1 and the numberto see if they are factors of the larger number. As you can see, checking a number in the billions would result inbillions 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 canquickly tell you if a number is NOT prime, but theycan not guarantee that a number IS prime. TheFermat testis the best-known of these. The trueprimality testsare 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 TestingIs 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 courseyour example is not prime, because it ends in 2 and all numbers that end in 2 are divisible by 2. There is nosimpleway to check whether a number is prime, butthere 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 primeand 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 youdon't get a 1. Then you know the numberISN'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 numberisa prime. But there are fancier versions of this basic idea that will tell you a number isalmost certainly a primeif 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 useTrial 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 thegreatest common divisord of a and N. If d > 1, thenN 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, thenN 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 theFermat 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 involved26 squaringsof 8-digit numbers,15 multiplicationsby 3, and26 divisionsby N. This is slightly less work than900-odd divisionsof 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.

Pingback: Prime Numbers: Checking for a Prime (Part 2) – The Math Doctors