1
$\begingroup$

In my lecture notes it is written that $a \equiv b \mod n$ with $a, b, n \in \Bbb Z$ could also be understood in the sense that $a$ divided by $n$ gives $b$ as a remainder. I don't see why this should be true though.

Take $a = 5, \ b = 11$. Obviously $5 \equiv 11 \mod 3$, but $5$ divided by $3$ does not give $11$ as a remainder. What am I missing here?

$\endgroup$
  • $\begingroup$ You are right. Maybe the notes use this convention (ie, assume that $b$ is the remainder). This is not incorrect, because in $\mathbb{Z}/n\mathbb{Z}$ we can select each representant of the equivalence class (arbitrarily) $\endgroup$ – Martín Vacas Vignolo Dec 28 '17 at 11:27
  • $\begingroup$ If you are ok, you can accept the answer and set as solved. Thanks! $\endgroup$ – gimusi Dec 29 '17 at 20:52
2
$\begingroup$

Well $5\equiv11 \pmod 3$ is also the same as $5\equiv 2 \pmod 3$.

From the division algorithm, we know

$$p=s\cdot q+r$$

where $r$ is the remainder and is less than $q$.

Then let $p=5$, $q=3$ and $r=11$ (from your example):

\begin{align} 5&=s\cdot 3+11\\ 3s& = -6 \\ s & = -2 \end{align}

Technically, this still works, though some might argue that the condition $q \gt r$ should exist. Think of congruences as a way to find the remainder, but keep in mind that there's flexibility in that definition.

$\endgroup$
1
$\begingroup$

I think you're confusing

  • $a\equiv b \mod n$, also denoted $a\equiv b \pmod n$, which means that $a$ and $b$ have the same remainder when divided by $n$;
  • and $a\bmod n=b$ (note the different spacing between $a$ and $\bmod$!), which means that the remainder of $a$ divided by $n$ is $b$, which is often implemented in CAS as the function mod(a;n) or something similar.
$\endgroup$
1
$\begingroup$

Since

$$a\equiv b \pmod n \iff a= kn+b \iff a=hn+r \ \land \ b=jn+r$$

the statement is true in the sense that $a$ divided by $n$ gives $b$ as a remainder mod n (and viceversa).

In your example:

$$5\equiv 11 \pmod 3 \iff 5= -2\cdot3+11\iff5=1\cdot3+2\ \land \ 11=3\cdot3+2$$

$\endgroup$

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.