Subject: intergers and number theory
Name: Eliseo
Who are you: Student

I was ask to pick any prime number greater than 3,square it ,then subtract 4, then divide the new result by 12 and record the remainder. He told me the remainder was 9.
How could he be sure that the remainder was 9 without knowing which prime I picked ?

Hello Elisio.

You don't have to pick prime numbers to see this happen, you can pick any odd number that is not divisible by 3 and you will get the remainder of 9. For example, 25 is not prime, but (25² - 4) modulus 12 = 9 as well.

The reason it works is this:

Let n be a positive odd number greater than or equal to 3. There is a positive integer i so that n = (2i+3). Then n² - 4 = 4i² + 12i + 5 = 4i(i + 3) + 5

Now if i is divisible by 3, then there exists some other integer a such that 3a = i, so
n² - 4 = 12a(3a + 3) + 5. So if we divide by 12, we get 5 as a remainder.

If (i - 1) is divisible by 3, then there exists some integer b such that 3b = i - 1 or in
other words, i = 3b + 1. So
n² - 4
= 4(3b + 1)(3b + 4) + 5
= 4(9b² + 15b + 4) + 5
= 12(3b² + 5b + 1) + 9.

So here we get 9 as a remainder if we divide by 12.

The last possibility is that (i - 2) is divisible by 3, so there exists some integer c
such that 3c = i - 2, or i = 3c + 2. So
n² - 4
= 4(3c + 2)(3c + 5) + 5
= 4(9c² + 21c + 10) + 5
= 12(3c² + 7c + 3) + 9

So here again we get 9 as a remainder.

All that's left is to convince yourself that all prime numbers greater than or equal to five are both odd and not divisible by 3.

Cheers,
Stephen La Rocque.