2
$\begingroup$

For example, if I compute $18 \bmod 5$, the result will be $3$. This will be because of $5\cdot3+3=18$, but can I have $5\cdot4-2=18$ which gives me $-2$?

5 Answers 5

0

Add a multiple of k to your negative number till it gets positive while youre looking for its k odulo value.

3

That is perfectly okay because they are in the same equivalency class. So, it isn't really that they have a different sign, it is just a different representative for that equivalency class (in the rationals, it is similar to $\frac{1}{2}=\frac{2}{4}$; same number, just different representatives for that equivalency class).

2

Things are more complicated than they ought to be. In Computer Science, $a\bmod m$ is the remainder when $a$ is divided by $m$. Since it is the remainder, we have $0\le a\bmod{m} \le m-1$.

Here "mod" is being used as a binary operator, much like addition or multiplication.

This notation is relatively seldom used by mathematicians. In mathematics, one writes $a\equiv b\pmod{m}$ if $m$ divides $a-b$. If $m$ is fixed, you can think of mod as a binary relation. With some variations, such as omitting parentheses, this has been standard notation since the time of Gauss.

To write $38\equiv -2\pmod{20}$ is perfectly correct.

To write $38\bmod{20}=-2$ is not correct: $38\bmod{20}=18$.

1

Yes. And note that $-2 \equiv 3 \mod 5$.

If we think of it in terms of cyclic groups, then if $r$ is the generator for $C_5$ we would be saying $r^{-2}=r^3$. I think people prefer to use 3 because the elements of $C_5$ are $\{r^0,r^1,r^2,r^3,r^4\}$, so $r^3$ (or 3) is actually in the group, whereas $r^{-2}$ needs you to work marginally harder by saying $r^{-1}$ is in the group first.

1

To answer the question in your title, the modulus (in your example, it is five) must always be at least $2$ for anything (interesting) to make sense. However, it is perfectly fine to write both $18 \equiv 3 \pmod{5}$ and $18 \equiv -2 \pmod{5}$ as $3 \equiv -2 \pmod{5}$.

As a general statement, we write $a \equiv b \pmod{m}$ to mean that $m \mid (a - b)$. Since $5 \mid (18 - (-2))$ and $5 \mid (18 - 3)$, both statements are correct. However, the division algorithm implies that given integers $q$ and $m$ with $m \geq 2$, then there exist unique integers $d$ and $r$ such that $q = dm + r$ and $0 \leq r < m-1$. Since $0 \leq r < m-1$, most mathematicians usually write $q \equiv r \pmod{m}$ where $0 \leq r < m-1$ as this is the natural choice for a member of the congruence class.