0

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.

Erulk
  • 15
  • "$n$ divides $a-b$" is the usual definition of $a\equiv b \pmod n$, so what's yours? – fkraiem Nov 21 '15 at 11:49
  • @fkraiem: Often the definition of $a\equiv b \pmod{n}$ is that $a$ and $b$ both leave the same remainder upon division by $n$. – paw88789 Nov 21 '15 at 11:51
  • I get this, I also understand that it implies $a$ and $b$ have the same remainder in the euclidian division by $n$, but I don't get how it is proven here. – Erulk Nov 21 '15 at 11:54

2 Answers2

0

The congruence $a \equiv b \pmod n$ has 2 definitions which actually mean the same thing:

  1. The one you mentioned in Part one
  2. If $a \equiv b \pmod n$, then both $a$ and $b$ on being divided by $n$ leave the same rest/remainder.
SchrodingersCat
  • 24,472
  • One should prove that these two 'definitions' are in fact equivalent; which seems to be the crux of the question. – paw88789 Nov 21 '15 at 11:53
  • @paw88789 The OP has mentioned the proof in his question. I presume that the OP has failed to realise that the 2nd definition is just a re-statement of the 1st definition. – SchrodingersCat Nov 21 '15 at 11:56
  • Yes, and this is how they came to the conclusion that bugs me. – Erulk Nov 21 '15 at 11:56
  • @Erulk You want me to explain you the proof. Is it so? Which part confuses you? – SchrodingersCat Nov 21 '15 at 11:57
  • My main concern was: "Does that mean because we divided $a$ and $b$ with the same number $n$ we should get the same remainder?" – Erulk Nov 21 '15 at 11:58
  • @Erulk It does not mean so. Say $a=11$ and $b=6$ and $n=4$. We don't get the same remainder in both cases. It means that if $a \equiv b \pmod n$ holds then only you will have the same remainder. The 2 definitions are truly re-statements of each other. – SchrodingersCat Nov 21 '15 at 12:01
  • Okay, I should reconsider the issue. It's more about how we came from "The remainder of the euclidian division being unique, it comes that $r$ is the remainder of the euclidian division of $a$ by $n$." to "We can deduce from that $a$ and $b$ have the same remainder in the euclidian division of $a$ by $n$." – Erulk Nov 21 '15 at 12:05
  • It has been stated earlier in the proof that on dividing $b$ by $n$, you have $r$ as the remainder. Check that. Then It says you divide $a$ by $n$ and you again get the remainder $r$. Get it? – SchrodingersCat Nov 21 '15 at 12:12
0

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

paw88789
  • 40,402