Equivalence Relations on Integers: Proving Equivalence for All Elements

[doggie_Walkes]

This is a question from A consise introduction to pure mathematics (Martin Liebeck)

Hi guys, just stuck on one problem was wondering if someone could lend me hand.

Let ~ be an equivalence relation on all intergers with the property that for all "m" is an element of the set of intergers , we have,

m ~ m +5
and also m ~ m+8

Prove that m~ n for all m, n is an element of intergers.

This is on page 161 of Martin Liebeck's book, number 7.

Im really stuck!

 

[Dick]

If you could show m~m+1 that would do it, right? Can you show m~m+5 and m~m+8 imply that?

 

[HallsofIvy]

This is a question from A consise introduction to pure mathematics (Martin Liebeck)

Hi guys, just stuck on one problem was wondering if someone could lend me hand.

Let ~ be an equivalence relation on all intergers with the property that for all "m" is an element of the set of intergers , we have,

m ~ m +5
and also m ~ m+8

Prove that m~ n for all m, n is an element of intergers.

This is on page 161 of Martin Liebeck's book, number 7.

Im really stuck!

For example, 6= 1+ 5 so 1 and 6 are equivalent. But 11= 6+ 5 so, because of the "transitive property, 1 is equivalent to 11. And, since 9= 1+ 8, 9 is also equivalent to 1 and therefore equivalent to 6 and 11. But 9= 4+ 5 so 9 is also equivalent to 9 and therefore to 1, and 6, and 11.

It looks to me like this is saying that two numbers, m and n are equivalent if and only if m= n+ 5i+ 8j for some integers 5 and 8. And that is same as saying m- n= 5i+ 8j. Let k= m-n. If you can show that any integer, k, can be written k= 5i+ 8j for some integers i and j, you have it.

I can show, using the Euclidean division algorithm, that for any integer k, i= -3k and j= 2k will work. Can you get that?

 

[doggie_Walkes]

Yeah kind of, not 100% sure.

I know its a equibalence relations, so don't we have to prove that it is reflexsive, symmetric, and transitive?