# Proving equivalence relation and classes

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

• 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$. – 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!

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