Proof Involving mod 5Date: 10/27/2002 at 15:35:58 From: Marjorie Preston Subject: Proof involving mod 5 I have a Discrete Math assignment, to prove the following: Prove n^2 mod 5 = 1 or 4 when n is an integer not divisible by 5. I can see that it's true, but don't know how to prove it. I know that the possible remainders for mod 5 are 0-4; I know that multiples of 5 all end in 0 or 5... It's interesting that the only squares less than 5 are 0, 1, and 4; and 5 divides 0, so we're left with 1 and 4.... What's the formula I'm missing? Does it have anything to do with primes? Any insight would be appreciated. Thanks! Date: 10/27/2002 at 19:49:11 From: Doctor Paul Subject: Re: Proof involving mod 5 You've already done the problem... Given an integer n, there are five possibilities: n = 0 mod 5 n = 1 mod 5 n = 2 mod 5 n = 3 mod 5 n = 4 mod 5 If n = 0 mod 5, then 5 divides n. We discard this case since it is the noted exception given above. Now we proceed just as you noted above: if n = 1 mod 5, then n^2 = 1^1 = 1 mod 5 if n = 2 mod 5, then n^2 = 2^2 = 4 mod 5 if n = 3 mod 5, then n^2 = 3^2 = 9 = 4 mod 5 if n = 4 mod 5, then n^2 = 4^2 = 16 = 1 mod 5 Thus when 5 does not divide n, n^2 = 1 mod 5 or n^2 = 4 mod 5. That's all there is to it... I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 10/27/2002 at 22:51:22 From: Marjorie Preston Subject: Thank you (Proof involving mod 5) I'm shocked by your quick reply! Thank you so much! Yes, it answers the question completely and provides the missing link in my thinking that I was looking for. You are good! Thank you thank you thank you! -Marjorie Preston |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/