Divisibility of Squares of Prime Numbers

Date: 02/14/98 at 00:06:59
From: M. Stryk
Subject: number theory

Suppose that p is any prime number greater than 3. Prove that p^2 
leaves a remainder of 1 when it is divided by 12.

Date: 02/20/98 at 15:43:45
From: Doctor Martin
Subject: Re: number theory

Good question -- here's the solution:

First, note that, given a prime p greater than 3, let m be the 
remainder you get when you divide p by 12. Then m is equal to either 
1, 5, 7, or 11. For if m were even, then p would be even, and greater 
than 3, so it wouldn't be prime.  Moreover, if m were equal to 0, 3, 
6, or 9, then p would be divisible by 3, and greater than 3, therefore 
not prime. Thus p = 12r + m, for some non-negative integer r, and with 
m = 1, 5, 7, or 11, as said before.  

Hence, p^2 = (12r + m)^2 = 144r^2 + 24rm + m^2. Therefore, the 
remainder you get when you divide p^2 by 12 is the same as the 
remainder you get when you divide m^2 by 12, since 144 and 24 are both 
divisible by twelve. I'll leave the rest to you -- just figure out 
what the possible remainders are when you divide m^2 by 12, when m = 
1, 5, 7, or 11. 

For more general methods of solving problems like this, you might try 
an elementary book on number theory, or look for information on 
modular arithmetic. Hope this helps...

-Doctor Martin, The Math Forum
 Check out our web site http://mathforum.org/dr.math/