3
$\begingroup$

Take the relation $R$ to be defined on the set of integers:

$aRb \iff 5 \mid (a + 4b)$

As part of a larger proof, I have to show that $R$ is both symmetric and transitive. I'm lost.

I see the first steps, but I can't find how to progress further. Here's what I have at this point:


Proof of Symmetry

We have to prove that if $5 \mid (a + 4b)$, then $5 \mid (b + 4a)$. Clearly, this is true if $a = b$, but apart from that, it's unclear in my mind.

Proof of Transitivity

We have to prove that if $5 \mid (a + 4x)$ and $5 \mid (x + 4b)$, then $5 \mid (a + 4b)$.


I've fiddled around with sample values, but I still don't see it. I'm pretty lost here. Thoughts?

  • 0
    I've changed "Symmetric proof" to "Proof of Symmetry". "Symmetric proof" reads as if you are saying that the *proof* is (somehow) symmetric, rather than that the proof is a proof *about* symmetry. "Symmetry proof" would have been okay, too...2011-12-04

2 Answers 2

4

HINT $\rm\ \ a\:R\:b\ \iff\ a-b\in 5\:\mathbb Z\:.\:$ If so, negating yields that $\rm\: b-a\in 5\:\mathbb Z\: $ hence $\rm\:R\:$ is symmetric. Transitivity follows by addition: $\rm \ a-b\:,\ b-c\:\in 5\:\mathbb Z\ \Rightarrow\ a-b + b-c\ =\ a-c \in 5\:\mathbb Z\:.$

Hence symmetry arises from $\rm\:5\:\mathbb Z\:$ being closed under negation, and transitivity arises from $\rm\:5\:\mathbb Z\:$ being closed under addition, i.e. from it being an additive subgroup of $\rm\mathbb Z\:.$ The innate algebraic structure will be brought to the fore when you study congruences and ideals of rings.

1

Symmetry: If $5\mid a+4b$, does $5\mid \big((a+4b)-(5a+5b)\big)$?

Transitivity: If $5\mid a+4x$ and $5\mid x+4b$, what can you say about $(a+4x)+(x+4b)$? How is this number related to $a+4b$?

  • 0
    $(a+4x)+(x+4b)=(a+4b)+5x$, so $a+4b=(a+4x)+(x+4b)-5x$. What do you know about each of the three terms on the righthand side?2011-12-04