You are currently browsing the tag archive for the ‘witness numbers’ tag.

Witness Numbers: Finding Primes

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!

Website Stats

• 8,562,561 views

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.

Explore here!

Free HL Paper 3 Questions P3 investigation questions and fully typed mark scheme.  Packs for both Applications students and Analysis students. A Super Exploration Guide with 168 pages of essential advice from a current IB examiner to ensure you get great marks on your coursework.