# Prove K^2 mod 4 = 1 ?

• Dec 14th 2012, 03:10 PM
brianjasperman
Prove K^2 mod 4 = 1 ?
This is my first post(Clapping)

I have been working on this for far too long:(

Can someone let me know if this is correct?

"k = 2n + 1. Then k^2 (is congruent to) 4n^2 + 4n + 1 (is congruent to) 1 mod 4"

Should I add more to it? Am I at least on the right track?
• Dec 14th 2012, 03:22 PM
chiro
Re: Prove K^2 mod 4 = 1 ?
Hey brianjasperman.

What you did is correct but if your teacher is picky you should probably write 4n^2 + 4n + 1 = 4(n^2 + n) + 1 = 4m + 1 just to add that extra clarity to the proof.
• Dec 14th 2012, 03:40 PM
brianjasperman
Re: Prove K^2 mod 4 = 1 ?
So I would prove the equation by saying:
"k = 2n + 1. Then 4n^2 + 4n + 1 = 4(n^2 + n) + 1 = 4m + 1"

OR

"k = 2n + 1. Then k^2 (is congruent to) 4n^2 + 4n + 1 (is congruent to) 1 mod 4, and 4n^2 + 4n + 1 = 4(n^2 + n) + 1 = 4m + 1"

Thanks for the help:)
• Dec 14th 2012, 03:42 PM
chiro
Re: Prove K^2 mod 4 = 1 ?
Basically 4m + 1 where m is an integer implies congruence to 1 (MOD 4) and you're done.
• Dec 14th 2012, 03:47 PM
brianjasperman
Re: Prove K^2 mod 4 = 1 ?
Thank you very very much for your help chiro, but I'm not understanding what your saying.

Can you show me what the entire proof would be (for Christmas?).
• Dec 14th 2012, 03:51 PM
chiro
Re: Prove K^2 mod 4 = 1 ?
Let k = 2n + 1 where n is an integer (in Z).

Then k^2 = (2n + 1)^2 = 4n^2 + 4n + 1 = 4(n^2 + n) + 1 = 4m + 1 for some integer m (m in Z).

By the definition of congruence something is congruent z = r (MOD q) iff z = pq + r where 0 <= r < q for some integers p, r, q and z.

By letting z = k^2, p = m, r = 1, and q = 4 and noting 0 <= 1 < 4 and all variables are integers, we get our condition that

k^2 = (1 MOD 4)