p 2 divided by 1 2
As p ranges over all prime numbers, how many possibilities are there for the remainder when p 2 is divided by 12?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Nice solution. My approach was to note first that any prime p > 3 can be written as either 6 k + 1 or 6 k − 1 for some positive integer k .
Then p 2 = 3 6 k 2 ± 1 2 k + 1 = 1 2 ( 3 k 2 ± k ) + 1 ⟹ p 2 ≡ 1 ( m o d 1 2 ) .
Adding in the special cases p = 2 and p = 3 we see that the only possible remainders mod 1 2 are then 1 , 4 and 9 .
Log in to reply
Hello Brian I always enjoy reading your solutions .I must confess that Iam not at your level of expertise but I do my best .Ialso like your comments on the solutions of other contributors - always kind gracious and courteous .
Log in to reply
Thanks, Des. I appreciate the compliments. I enjoy this site in part because the interactions between members are so respectful, (for the most part). It's quite gratifying to see how much young talent there is out there from all over the world. They are well ahead of where I was in my teens. :)
Yes, that was the approach I was thinking of. It is well-known that if p > 3 , then p 2 ≡ 1 ( m o d 1 2 ) .
I was thinking of how to play with this fact, and so came up with this question.
Thanks for answering this! I thought that people didn't like this question after all.
Log in to reply
Sometimes it's just a matter of timing whether a question gets noticed or not. I liked this question, so I'll reshare it and see if it gets more attention. :)
I loved the question sir as the fact that any prime greater than 3 squared and divided by 12 leaves a remainder of 1. So the only other cases are squares of 2 and 3. Nice problem again and sir I have to appreciate the number of problems you post with which I have learnt so much and this makes Brilliant better and better.
Using Euler's theorem:
p 2 ≡ 1 ( m o d 4 ) if p and 4 are coprime
and
p 2 ≡ 1 ( m o d 3 ) if p and 3 are coprime
12 is a multiple of both 3 and 4 so as long as p is coprime to 3 and 4 it gives a remainder of 1 when divided by 12. The only primes not coprime to 3 and 4 are 2 and 3.
So 2 2 ≡ 4 ( m o d 1 2 )
3 2 ≡ 9 ( m o d 1 2 )
p 2 ≡ 1 ( m o d 1 2 ) , p>3
Therefore there are 3 possible remainders.
Nicely done!
For every odd integer (not necessarily prime) z , its square z 2 has remainder 1 or 9 divided by 1 2 (very easy to prove).
Among the odd primes there are numbers that assume both these possible values (namely 3 and 5 ).
Adding the remainder of the only even prime squared (that is 4 ) we have only three possible remainders for a prime squared divided by twelve.
Working with all odd integers and then showing that the primes also hold is an interesting way of approaching this. I didn't think of it like that. Thanks for sharing :)
Consider p 2 − 1 = ( p + 1 ) ( p − 1 ) , p > 3 . One of p , ( p − 1 ) , ( p + 1 ) must be divisible by 3 , but since p is a prime greater than 3 , it can't be divisible by 3 . So one of ( p + 1 ) , ( p − 1 ) is divisible by 3 .
Next, since p is odd, both ( p + 1 ) and ( p − 1 ) are even and one of them is divisible by 4 .
Therefore, p 2 − 1 is divisible by 3 and 4 , and in turn, divisible by 1 2 . So p 2 ≡ 1 ( mod 1 2 ) .
Finally we just have to check the two remaining cases, p = 2 and p = 3 , which give a modulus 1 2 of 4 and 9 . There are 3 distinct remainders, namely 1 , 4 , 9 . (Neat! Recognize those numbers? They're pretty famous.)