Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
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 5

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
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.

share|improve this answer
    
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$

share|improve this answer
    
@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 ?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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