[Discrete Math] Relations, symmetric and transitive

[Servo888]

Ok so here's one of the questions we've been assigned...

Let ~ be a relation on th integer such that for every a,b (integers) we have a ~ b iff 5 | a^2+4b^2 Prove or disprove the following: b) ~ is symmetric, c) ~ is transitive

So I can graphically see what this relation looks like, and from that I've shown it's reflexive. Now I'm working on proving it as being symmetric, but I can't put it into words.

b) ~ is symmetric. Well we want to show that aRb -> bRa, so 5 | a^2+4b^2 -> 5 | b^2+4a^2. Well I can see graphically once again that b^2+4a^2 will always give me a multiple of 5 - this is what I can't put into words... I can't really figure out how to express aRb -> bRa... From another help source I was told this;

5 | a^2+4b^2 iff 5 | a^2-b^2, so then I was told to a^2+4b^2 - a^2-b^2 = 5b^2, which is a multiple of 5. But I don't see how the hell that works... But it's based on some equivalance class, modulous 5 (maybe?) that's 4 = -1...

c) ~ is transitive. Graphically this looks true. We need to show that aRb and bRc -> aRc. But I'm not sure where to start on this... I don't see where c fits in.

 

[HallsofIvy]

That 5 divides a²+ 4b² if and only if 5 divides a²- b² is a very good hint! Of course, it's clear that it is true: if 5 divides a²- b² then it certainly divides a^b- b²+ 5b² and vice versa.

The point is that if a²+ 4b² is not obviously "symmetric" but a²- b² certainly is: if a²- b² is divisible by 5 then b²- a²= -(a²- b²) certainly is!

Once again, that lovely "5 divides a²+ 4b² if and only if 5 divides a²- b²" is key. If 5 divides a²- b² and 5 divides b²- c² then what can you say about a²- c²= (a²- b²)- (b²- c²)?

 

[Servo888]

a^2 - b^2 is obviously symmetric? I don't see it =\ can you explain this further?

[edit] Ohh... So it's like aRb -> bRa (for all a,b in some set). I see it now. But I don't see why we are using a^2-b^2, where did it come from? What made you say, oh well 5|a^2+4b^2 iff 5|a^2-b^2.

 

[Servo888]

Once again, that lovely "5 divides a²+ 4b² if and only if 5 divides a²- b²" is key. If 5 divides a²- b² and 5 divides b²- c² then what can you say about a²- c²= (a²- b²)- (b²- c²)?

That 5 must also divide a²- c²= (a²- b²)- (b²- c²) since aRb^bRc -> aRc

 

[matt grime]

Adding (or subtracting) a multiple of 5 doesn't alter the divisibilty or indivisibilty by 5 of a number. That's just basic modulo arithmetic.

a^2-b^2 = a^2+4b^2 -5b^2

hence one side is divisible 5 if and only if the other side is.

and since a^2-b^2=-(b^2-a^2)

it is obviously a symmetric relation.

 

[Servo888]

Adding (or subtracting) a multiple of 5 doesn't alter the divisibilty or indivisibilty by 5 of a number. That's just basic modulo arithmetic.

a^2-b^2 = a^2+4b^2 -5b^2

hence one side is divisible 5 if and only if the other side is.

and since a^2-b^2=-(b^2-a^2)

it is obviously a symmetric relation.

I can follow this really well; but never in a million years would I have used the idea that I could just subtract a mulitple of 5... But yes, this now makes sense.