Proving n2 is Not Congruent to 2 (mod6) for All Integers: Discrete Math Help

[mamma_mia66]

Homework Statement

Show that n^{2 \neq}2 (mod6) for all n in Z

Homework Equations

The Attempt at a Solution

0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

I did only the table for mod 6 and then I don't have an idea what to do.
I am not even sure if I understand what exactly I have to do with this problem.
Please help me if you can.

 

[gabbagabbahey]

Hmmm...have you tried proof by contradiction? That is, assume that n^2 \equiv 2 \pmod{6}...what does that imply?

 

[VeeEight]

I did not attempt a solution but you might want to rewrite the statement.

n² congruent to 2 mod 6 is the same as n² - 2 is a multiple of 6. So you might want to define f(n) = n² - 2 and show what happens when you divide f(n) by 6.

 

[mamma_mia66]

I think the only hint I get for this was the reminder needs to be \neq2.

I am gessing that has something to do with division Algorithm. I will try the above ideas.

 

[Mark44]

VeeEight said that "n^2 congruent to 2 mod 6 is the same as n^2 - 2 is a a multiple of 6."

That's also the same as saying that n^2 - 2 \equiv 0 mod 6.

This one is ripe for a proof by induction.

 

[mamma_mia66]

I don't think I know how to do it by induction. Thank you. I will try and I will come back again.

 

[Mark44]

Pick a value of n for which your statement is true, such as n = 2.

Assume that for n = k, your statement is true. IOW, assume that k^2 != 2 mod 6.
Now show that for n = k + 1, (k + 1)^2 != 2 mod 6, using the induction hypothesis (the thing you assumed in the previous step).