I've been working on congruences these days and figured out the core concept behind this notion. However I fail to understand a part of the demonstration:
- Part 1 was about proving that if $a\equiv b\pmod n$ then $n$ divides $a-b$. I got it, it was simple.
- Part 2 is focused on proving the "if and only if" of the theorem: $a\equiv b\pmod n$ $\Leftrightarrow$ $n$ divides $a-b$
Let's assume $n$ divides $a-b$. There is an integer $k$ such as $a-b=kn$, so $a=b+kn$. $r$ being the remainder of the euclidian division of $b$ by $n$, then $b=nq+r$ with $q$ integer and $0 \leq r \lt n$. Therefore, $a=nq+r+kn$ that is $a=n(q+k)+r$ with $0 \leq r \lt n$ and $q+k$ integer. The remainder of the euclidian division being unique, it comes that $r$ is the remainder of the euclidian division of $a$ by $n$.
I understand this part but here comes the issue:
We can deduce from that $a$ and $b$ have the same remainder in the euclidian division of $a$ by $n$.
How? Does that mean because we divided $a$ and $b$ with the same number $n$ we should get the same remainder? Thanks in advance for explaining it to me.
Note: the demonstration was originally in another language and I translated it, so there might be a little confusion somewhere. If it's the case please tell me.
Looking at the proof (your first yellow box): Dividing $b$ by $n$ gives a unique quotient and remainder (rest): $b=nq+r$.
The observation that $a-b=kn$, along with a little algebra allows us to write $a=n(q+k)+r$.
But dividing $a$ by $n$ gives $a=nt+s$ where $s$ is a valid remainder. By uniqueness in the division algorithm, we must have $t=q+k$ and $s=r$.
So indeed $a$ and $b$ leave the same remainder upon division by $n$. So $a\equiv b \pmod{n}$