Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proof Involving mod 5

Date: 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
Associated Topics:
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/