Modulo with negative numbers

Question

When I input this in wolfram I get false

-347 mod 6 = 5

When I input this I get true

-347 mod 6 = 1

And yet I know

$-5 \equiv 1$

And additionally

$-6*57 - 5 = -347$

but

$-6*57 - 1 \neq -347$

So it's strange that Wolfram's answer is true for +1

Why does Wolfram answer it that way?

What's so strange? $6 \times -57 + (-5) = -347$ so $-347\equiv -5\equiv +1$. — kennytm, May 14 '16 at 06:39

Soham · Accepted Answer · 2016-05-14T06:46:10.010

2

$a\equiv b\pmod c$ means $c|(a-b)$

$-347\equiv1\pmod6$ is true because $6$ divides $(-347-1)=-348$

But,$-347\equiv5\pmod 6$ is not true because $6$ does no divide $(-347-5)=-352$.

edited May 14 '16 at 06:46

answered May 14 '16 at 06:40

Soham

9,990

So if the dividend is negative, I add the remainder to the modulus? – the_prole May 14 '16 at 06:53
@the_prole It depends on the sign of the divisor.... – Soham May 15 '16 at 14:35

score 0 · Answer 2 · answered May 14 '16 at 06:42

$$-347=5\pmod6\iff -347-5=0\pmod 6\iff 6\,\mid\,-352$$

and we can easily check that in fact $\;6\,\nmid\,-352\;$.

Yet

$$-347=1\pmod6\iff -347-1=3-248=0\pmod 6\;,\;\;\text{and}\;\;-348=(-58)\cdot6$$

What you say would be odd if we had $\;5=1\pmod6\;$ (in fact, it'd impossible), but we don't. We have $\;5=-1\pmod6\;$, and $\;1\neq-1\pmod6\;$

score 0 · Answer 3 · answered May 14 '16 at 07:02

$-347 \pmod 6$ cannot be congruent to both 5 and 1 because these two numbers differ by 4 (and not by 6).

You can always subtract or add multiples of 6 to either side of an equation and it will still hold. For example, since $-347 \pmod 6 = 1$, repeatedly adding 6 to -347 (i.e. -341, -335, -329, etc) will eventually hit 1. Before reaching 1, it was equal to -5. The next number after 1 is 7. So we will never the number 5 in such a sequence.

Modulo with negative numbers

3 Answers3

Linked