Register to reply 
Need descrete math help 
Share this thread: 
#1
Nov908, 07:52 PM

P: 52

1. The problem statement, all variables and given/known data
Show that n^{2 [tex]\neq[/tex]}2 (mod6) for all n in Z 2. Relevant equations 3. 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. 


#2
Nov908, 07:59 PM

HW Helper
P: 5,004

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



#3
Nov908, 08:02 PM

P: 612

I did not attempt a solution but you might want to rewrite the statement.
n^{2} congruent to 2 mod 6 is the same as n^{2}  2 is a multiple of 6. So you might want to define f(n) = n^{2}  2 and show what happens when you divide f(n) by 6. 


#4
Nov908, 08:11 PM

P: 52

Need descrete math help
I think the only hint I get for this was the reminder needs to be [tex]\neq[/tex]2.
I am gessing that has something to do with division Algorithm. I will try the above ideas. 


#5
Nov908, 08:57 PM

Mentor
P: 21,216

VeeEight said that "n[tex]^2[/tex] congruent to 2 mod 6 is the same as n[tex]^2[/tex]  2 is a a multiple of 6."
That's also the same as saying that n[tex]^2  2 \equiv[/tex] 0 mod 6. This one is ripe for a proof by induction. 


#6
Nov1008, 07:24 AM

P: 52

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



#7
Nov1008, 02:13 PM

Mentor
P: 21,216

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). 


Register to reply 
Related Discussions  
Mixed Quantifers confusion! Descrete Math  Calculus & Beyond Homework  4  
Quantified statement logic question, descrete math, wee!  Calculus & Beyond Homework  2  
Can someone see if i found the correct Truth set of the predicate, descrete math fun!  Calculus & Beyond Homework  4  
Descrete Math logic confusion!  Calculus & Beyond Homework  2  
Can some clarify I did this logical expressoin correctly? descrete math  Calculus & Beyond Homework  3 