The Numberphile video above is an excellent introduction to primality tests – where we conduct a test to determine if a number is prime or not. Finding and understanding about prime numbers is an integral part of number theory. I’m going to go through some examples when we take the number 2 as our witness number. We have a couple of tests that we conduct with 2 – and for all numbers less than 2047 if a number passes either test then we can guarantee that it is a prime number.

Miller-Rabin test using 2 as a witness number:

We choose an odd number, n >2. First we need to write it in the form:

Then we have to conduct a maximum of 2 different tests:

If either of the above are true then we have a prime number.

Testing whether n = 23 is prime.

First we need to write 23 in the following form:

Next we need to check if the following is true:

Remember that mod 23 simply means we look at the remainder when we divide by 23. We can do this using Wolfram Alpha – but in this case let’s see how we could do this without a calculator:

Therefore this passes the test – and we can say that it is prime.

Testing whether 1997 is prime

For 1997 we have:

So we need to first test if the following is true:

However using Wolfram Alpha we get:

So this fails the first part of the test.

Trying the second part of the test, we need:

We have already tested the case when r=0 (this gives the earlier result), so just need to look at what happens when r=1. Again we use Wolfram Alpha to get:

This passes the 2nd part of the test and so confirms that 1997 is prime.

What happens with 2047?

2047 is not prime as we can write it as 2 x 3 x 11 x 31. However it is the first number for which the witness 2 gives a false positive (i.e we get a positive result even though it is not prime). We write 2047 as:

But we do indeed get:

So we can call 2047 a pseudoprime – it passes this prime number test but is not actually prime.

Larger primes

For numbers larger than 2047 you can combine witnesses – for example if you use both 2 and 3 as your witness numbers (and regard a positive result as at least one of them returning a positive result) then this will find all primes for n < 1,373,653.

More interestingly for extremely large numbers you can use this test to provide a probability estimate for the likelihood that a number is prime. Lots to explore here!

All content on this site has been written by Andrew Chambers (MSc. Mathematics, IB Mathematics Examiner).

New website for International teachers

I’ve just launched a brand new maths site for international schools – over 2000 pdf pages of resources to support IB teachers. If you are an IB teacher this could save you 200+ hours of preparation time.

## Leave a comment

Comments feed for this article