Divisibility of Squares of Prime NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/