# Question in Number theory about primes greater than 3

The Question says prove that the square of every prime number greater than 3 yields a remainder of 1 when divided by 12.

My approach was that since every prime can be written as $6k\pm 1$ and when we square this expression we get in both cases $36k^2+12k+1$. Taking 12 common from the first two terms of the expression we get $12(3k^2+k)+1$.

So $12a+1$ where $a = (3k^2+k)$ yields a remainder 1 upon division with 12 right? Is this correct and if it is is there a more elegant proof?

Any help would be appreciated.

• Hint: the squares $\pmod {12}$ are $\{0,1,4,9\}$. – lulu Dec 28 '17 at 16:10
• – lab bhattacharjee Dec 28 '17 at 16:13
• Odd squares are equivalent to $1\bmod 8$ whence you could replace $12$ by $24$ – Mark Bennet Dec 28 '17 at 16:27

Yes, that's correct. There are a number of different ways to do it (as comments and other answers are demonstrating), but yours isn't too cumbersome.

• then give a better proof for this here – Dr. Sonnhard Graubner Dec 28 '17 at 16:17
• lulu hinted at one in the comments; yours in your answer is particularly nice (which is why I upvoted it!) But I think the OP's proof is fine; I wouldn't call it inelegant. – BallBoy Dec 28 '17 at 16:21
• @Y.Forman What does OP stand for? – Prakhar Nagpal Dec 28 '17 at 17:19
• @PrakharNagpal "Original Poster," i.e., the poster who asked the question – BallBoy Dec 28 '17 at 17:25

If $p$ is a prime greater than 3, then $p \equiv 5$ or $7 \pmod{12}$, which is just another way of saying $p = 6k \pm 1$. Then $p^2 \equiv \pmod{12}$.

This is not necessarily better, just more concise. Speaking only for myself, I was satisfied when I saw $36k^2 + 12k + 1$. My mind immediately went to $$\frac{36k^2 + 12k + 1}{12} = 3k^2 + k + \frac{1}{12}$$ but I hadn't thought of that concretely until just now. Eventually this sort of thing will become automatic for you.

Okay, $6k \pm 1$, good, $36k^2 + 12k + 1$, good, good. At this point you can optimize: what's the remainder of $36k^2$ divided by $12$? That would be $0$, so you can just chuck $36k^2$, leaving you with $12k + 1$. And then the remainder of $12k$ divided by $12$ is also $0$, so you can chuck $12k$ as well, leaving you with... just $1$. And done.

write $$p^2-1=(p-1)(p+1)$$ and since $$12=3\cdot 4$$ the product is divisible by $3$ and since $p-1$ and $p+1$ are even the product is divisible by $12$