Definition of modular congruence with divisibility

Question

My notes have the following definition for congruence which I do not understand.

$a \equiv_n b \Leftrightarrow n \mid (a-b)$

I know that $a \equiv_n b$ is $a (mod\,n) = b (mod\,n)$ but I'm not sure where the above definition comes from.

Answer 1

Let's suppose we have integers such that $a = nk+r; 0\le r < n $ and $b = nj+r ;0 \le r < n $ then $a $ and $b $ have the same remainder, $r $, when divided by $n $.

If so, then $a-b=(nk+r)-(nj+r)=nk-nj=n (k-j) $. This means $a-b $ is a multiple of $n $ and $n$ divides $a-b $.

Likewise if we suppose we have integers such that $n$ divides $a-b$, that would mean $a-b=n*m $ for some $m $. If $b $ has remainder $r $ when divided by $n $, the $b=kn+r $ for some $k $. $a = n*m +b= n*m+kn+r= n (m+k)+r $. So $a $ and $b $ have the same remainder when divided by $n $.

So the two statements: i) $n|a-b $ and ii) $a$ and $b $ have the same remainder; are equivalent to each other.

We define that property as:

$a \equiv b \mod n $

Or we sometimes use the notation:

$a\equiv_n b $.

===

Also note

If $a \equiv b \mod n $ then $a +k \equiv b+k \mod n $

So $a \equiv b \mod n \iff a-b \equiv 0 \mod n $.

Um... do you see that $X \equiv 0 \mod n \iff n|X $?

Answer 2

Note that $a \equiv b \pmod n$ means that a multiple $k$ of $n$ is equal to $a$ when adding $b$ units. We write this as: $a= kn + b$

So $a-b = kn$ means that $a-b$ is divisible by $n$ thus $n \mid (a-b)$.