I was wondering how I could prove

aRb if and only if 5 | (a + 4b) , on the set of all integers

I'm used to proving for sets of numbers so I have no idea how to start out for this... Equivalence relation I know means reflexive, symmetric and transitive, but how can I prove it for that relation?

And also how can I show the equivalence classes of R (the above relation)?

  • $\begingroup$ Note that $5 \mid a+4b$ iff $5 \mid a-b$. Hence $a R b$ iff $f(a) = f(b)$, where $f(n) = n \mod 5$. $\endgroup$ – copper.hat Nov 27 '14 at 6:02

$\def\r{\mathrel{\rm R}}$Remember that in proof problems, correct logic and clear setting out are both vital.

Reflexive. For any integer $a$ we have $5\mid 5a$ by definition of divisibility. This can be written as $$5\mid (a+4a)\ ,$$ and therefore $a\r a$. Thus $\r$ is reflexive.

Symmetric. Let $a,b$ be integers and suppose that $a\r b$. By definition, this means that $$5\mid(a+4b)\ .$$ But clearly $5\mid5(a+b)$, and so by well-known properties of divisibility, $$5\mid(5(a+b)-(a+4b))\ ,$$ that is, $$5\mid(b+4a)\ .$$ Thus $b\r a$. We have proved that if $a\r b$ then $b\r a$; so $\r$ is symmetric.

Transitive. The layout of the proof will be similar to the proof that $\r$ is symmetric (though of course the content will be different). Please try it for yourself.

Equivalence classes. For example, the equivalence class of $1$ is by definition the set of all $a$ such that $a\r1$; that is, the set of all $a$ such that $5\mid(a+4)$. This divisibility statement can be written $a+4=5k$, or $a=5k-4$. So the equivalence class of $1$ is $$[1]=\{5k-4:k\in{\Bbb Z}\}=\{\ldots,-9,-4,1,6,11,16,\ldots\}\ .$$ If you work out the rest for yourself I think you will soon realise that this relation is in fact just congruence modulo $5$, written in a slightly disguised way.

Good luck!

  • $\begingroup$ "But clearly 5∣5(a+b)" I don't understand your reasoning for this part! (In the symmetric explanation) $\endgroup$ – Patrick Nov 27 '14 at 6:07
  • $\begingroup$ The symbol $\mid$ means "is a factor of". $\endgroup$ – David Nov 27 '14 at 11:36
  • $\begingroup$ Youre using 1 as an example here, but since it's b we're talking about, it would be [b] = {5k-4b : k ∈ ℤ} ? $\endgroup$ – Patrick Nov 29 '14 at 6:22
  • $\begingroup$ And therefore {..., 5-4b, 10 - 4b, 15 - 4b,...}? $\endgroup$ – Patrick Nov 29 '14 at 6:28

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.