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