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 (252 - 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 n2 - 4 = 4i2 + 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
n2 - 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
n2 - 4
= 4(3b + 1)(3b + 4) + 5
= 4(9b2 + 15b + 4) + 5
= 12(3b2 + 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
n2 - 4
= 4(3c + 2)(3c + 5) + 5
= 4(9c2 + 21c + 10) + 5
= 12(3c2 + 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.
Stephen La Rocque.