Proving the remainder is $1$ if the square of a prime is divided by $12$

Given, $p$ is a prime number and $p>3$. How do we prove that the remainder $r$ is always $1$ if $p^2$ is divided by $12$?

-
Hint Consider separately the moduli $3$ and $4$. This reduces significantly the number of cases to be chacked. –  awllower May 23 '13 at 16:59

5 Answers

$p^2 -1 =(p-1)(p+1)$. Since p is odd, these are two even factors, so the product is divisible by 4. Also, one of p-1, p, p+1 must be divisible by 3, but since p is prime, it is not divisible by 3. Thus one of p-1, or p+1 must be divisible by three.

-

Hint: $\,3 < p\,$ prime $\,\Rightarrow\, p = 6n\pm 1\,\Rightarrow\, p^2 = 36n^2\pm12n+1$

-
won't you simplify a little ? –  lab bhattacharjee May 23 '13 at 17:33
@lab It's tagged homework. What do you think I should simplify? –  Key Ideas May 23 '13 at 17:35
sorry I was thinking about $24$ –  lab bhattacharjee May 23 '13 at 17:37

Hint: consider $0,1,2,\ldots, 11$, which are all the possible remainders modulo 12. Take out the ones that couldn't be congruent to a prime bigger than 3. Square all the ones that are left modulo 12, and see what you get.

-
I think I get what you are saying.Thanks. –  rahul May 23 '13 at 17:02

If $(a,12)=1, (a,3)=1$ and $(a,2)=1$

$(a,3)=1\implies a\equiv\pm1\pmod 3\implies a^2\equiv1\pmod 3$

$(a,2)=1\implies a$ is odd $=2b+1$(say) where $b$ is some integer

$(2b+1)^2=4b^2+4b+1=8\frac{b(b+1)}2+1\equiv1\pmod 8$

$\implies a^2\equiv1\pmod { \text{lcm}(3,8)}$

Now, lcm $(3,8)=24$

-
@Rahul, how about this one? –  lab bhattacharjee May 23 '13 at 17:24
bhattacharjee ,hmmm I never expected this many answers,but I thuik it is a fairly good one. –  rahul May 23 '13 at 17:30
@rahul, thanks. Hope I make my point clear. You may have a look into math.stackexchange.com/questions/398656/… –  lab bhattacharjee May 23 '13 at 17:35

Hint:

since $p>3$ we know that $p$ is not even. So the posibilities for $p$ mod$(4)$ are : $...$

consequently for $p^2$ mod$(4)$ are : $...$

and for $p$ mod$(3)$ are : $...$

consequently for $p^2$ mod$(3)$ are : $...$

If you did the right calculations you will see that in both cases $p^2\equiv 1$ mod$(4)$ and mod$(3)$ , so ?

-