4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ then give a better proof for this here $\endgroup$ – Dr. Sonnhard Graubner Dec 28 '17 at 16:17
  • $\begingroup$ 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. $\endgroup$ – BallBoy Dec 28 '17 at 16:21
  • $\begingroup$ @Y.Forman What does OP stand for? $\endgroup$ – Prakhar Nagpal Dec 28 '17 at 17:19
  • $\begingroup$ @PrakharNagpal "Original Poster," i.e., the poster who asked the question $\endgroup$ – BallBoy Dec 28 '17 at 17:25
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.