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?

$\endgroup$
3
  • 2
    $\begingroup$ $aRb$ iff $5\mid a-b$ iff $5\mid b-a$. $\endgroup$ – Did Dec 4 '11 at 22:34
  • 1
    $\begingroup$ a hint: $(a+4b) + (b+4a) = (5a + 5b)$ $\endgroup$ – deinst Dec 4 '11 at 22:36
  • $\begingroup$ 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... $\endgroup$ – Arturo Magidin Dec 4 '11 at 23:28
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ @deinst's comment cleared up the symmetry part for me, but I don't see why adding $a+4x$ to $x+4b$ helps us solve the transitivity part of the proof? $\endgroup$ – David Chouinard Dec 4 '11 at 22:52
  • $\begingroup$ $(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? $\endgroup$ – Brian M. Scott Dec 4 '11 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.