[Discrete Math] Relations, symmetric and transitive

  • Thread starter Servo888
  • Start date
  • #1
43
0
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 [tex]5 | a^2+4b^2[/tex] 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 [tex]5 | a^2+4b^2[/tex] -> [tex]5 | b^2+4a^2[/tex]. Well I can see graphically once again that [tex]b^2+4a^2[/tex] 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;

[tex]5 | a^2+4b^2[/tex] iff [tex]5 | a^2-b^2[/tex], so then I was told to [tex]a^2+4b^2 - a^2-b^2 = 5b^2[/tex], 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.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
966
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
43
0
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.
 
Last edited:
  • #4
43
0
HallsofIvy said:
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)?

That 5 must also divide a2- c2= (a2- b2)- (b2- c2) since aRb^bRc -> aRc
 
  • #5
matt grime
Science Advisor
Homework Helper
9,420
4
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
43
0
matt grime said:
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.
 

Related Threads on [Discrete Math] Relations, symmetric and transitive

Replies
17
Views
8K
Replies
5
Views
2K
Replies
7
Views
5K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
9
Views
11K
Replies
2
Views
462
Replies
2
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
4
Views
1K
Replies
2
Views
1K
Top