Discrete Mathematics with possible Quotient Remainder Theorem

[tennesseewiz]

Homework Statement

For all integers m, m[tex]^{}2[/tex]=5k, or m[tex]^{}2[/tex]=5k+1, or m[tex]^{}2[/tex]=5k+4 for some integer k.


Relevant equations
I'm pretty sure we have to use the Quotient Remainder THM, which is:

Given any integer n and positive integer d, there exists unique integers q and r such that,

n=dq+r and 0 [tex]\leq[/tex]r<d.

But that's as far as I got. I have no idea what to do next.

 

[StatusX]

Well, it seems pretty obvious what you want d to be. Then square it.

 

[tennesseewiz]

No, I have no idea what d is supposed to be. Are you saying that d should equal m and that d squared is m squared?

 

[StatusX]

Compare 5k+1 to dq+r.

 

[tennesseewiz]

Aaahhh...

So d=5, k=q, and r=1. Would n=m^2? But how would that help me. I mean if you take the square root then n might not possible be an integer anymore...

 

[genneth]

If you've encountered modular arithmetic, use

n (mod 5)     0  1  2  3  4
n^2 (mod 5)   0  1  4  4  1

 

[StatusX]

For any number m, you can write m=5q+r. So what is m²? Combine factors of 5 to see what the remainder is for different r.

 

[tennesseewiz]

Okay, I think I'm getting the general idea. I know that r can only be 0,1,2,3 or 4, but when m is squared, those numbers still have to be lower than five, so 0^2 is less than five, as is 1^2 and 2^2. Am I on the right track?

 

[Dick]

Yes, there are five possible remainders, but squared and taken mod 5 there are only three.