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. 
 A: 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.
A: 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.
A: 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.
A: 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$
