Question about a particular equivalence relation.

[frankfjf]

Homework Statement

Determine if this is an equivalence relation. Either specify which properties fail or list the equivalence classes:

A = {0, 1, 2...}
R = {(m,n) | m^2 ≡ n^2 mod 3}

Homework Equations

m^2 ≡ n^2 mod 3

The Attempt at a Solution

I've determined that it is indeed an equivalence relation, but my problem is when it comes to coming up with the equivalence classes. I'm used to the equation in the relation just using m and n instead of them being squared, so perhaps that's what's throwing me off.

[0] = {0, 3, 6, 9, ...} but unlike equivalence relations where [1] would be {1, 4, 7, 10, ...} the professor's solution says that [1] = {1, 2, 4, 5, 7, 8, ...}. Why is this? What happens in this particular equivalence relation that causes [1] to have that pattern? I know that you have to look at it as m^2 - n^2 = 3z, but how does the squaring change the pattern?

 

[NoMoreExams]

Which numbers squared are 1 mod 3? let's see... 1^2 = 1 mod 3, 2^2 = 4 = 1 mod 3, 4^2 = 16 = 1 mod 3... see a pattern?

 

[frankfjf]

Which numbers squared are 1 mod 3? let's see... 1^2 = 1 mod 3, 2^2 = 4 = 1 mod 3, 4^2 = 16 = 1 mod 3... see a pattern?

I think I'm starting to see what you mean, but when you say "Which numbers squared are 1 mod 3", do you mean like... which numbers when divided by 3 give a remainder of 3 or leave no remainder when divided by 3? I'm a little fuzzy on modulus in this situation, it's been a while.

 

[NoMoreExams]

n^2 mod 3 means take a number n, square it, divide it by 3 and tell me the remainder.

 

[frankfjf]

And everytime the remainder is 3, it goes in the equivalence class?

 

[NoMoreExams]

No, there will never be a remainder of 3, you are dividing by 3, how can you have a remainder of 3?

 

[frankfjf]

Well, 1 divided by 3 = 0.3 with the 3 repeating. 4 (or 2^2) divided by 3 is 1.3 with the 3 repeating, but 3/3 gives no remainder, it divides evenly into 1. Likewise 16 (or 4^2) is 5.3, again with the 3 repeating.

 

[NoMoreExams]

That's not what remainder is. If you take x and divide it by n then you have a*q + r so r is the remainder, for example 4 divided by 3 is 4 = 3*1 + 1, so the remainder is 1.

 

[frankfjf]

Ohhh. For some reason I had it in my head that the part after the decimal was the remainder. But is the .3 an indicator of what would be valid in the equivalence class for 1 mod 3?

 

[NoMoreExams]

Nope. The remainder of when you divide 1, 4, 16, 25, etc. by 3 is 1, hence it's in your equivalence class of [1]

 

[frankfjf]

Wait wait. Nevermind. I was overcomplicating it. Basically you mean, "which numbers when divided by 3 give you a remainder of 1, those numbers go in the equivalence class for 1."?

 

[NoMoreExams]

Well in this case, which numbers squared, divided by 3 give a remainder of 1?

 

[frankfjf]

Now I got it. Thank you so much, it was driving me crazy.