# [Discrete Math] Relations, symmetric and transitive

1. Feb 19, 2006

### Servo888

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

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.

2. Feb 19, 2006

### HallsofIvy

Staff Emeritus
That 5 divides a2+ 4b2 if and only if 5 divides a2- b2 is a very good hint! Of course, it's clear that it is true: if 5 divides a2- b2 then it certainly divides ab- b2+ 5b2 and vice versa.

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

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

3. Feb 19, 2006

### Servo888

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

 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.

Last edited: Feb 19, 2006
4. Feb 19, 2006

### Servo888

That 5 must also divide a2- c2= (a2- b2)- (b2- c2) since aRb^bRc -> aRc

5. Feb 19, 2006

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

6. Feb 19, 2006

### Servo888

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.