10
$\begingroup$

I am having trouble actually really understanding the modulo congruence.

I understand it intuitively very well. However, I fear that my background in development is not helping.

Writing:

$x \equiv y \pmod m$

Means that both $X$ and $Y$ belong have the same remainder after being divided by $m$. For example:

$17 ≡ 20 \pmod 3$

As they both belong to the same "class" of numbers with a reminder of $2$ when divided by $3$.

In MATHEMATICAL CRYPTOLOGY by Keijo Ruohonen confirms this:

The congruence $x ≡ y$ $mod$ $m$ says that when dividing $x$ and $y$ by $m$ the remainder is the same, or in other words, $x$ and $y$ belong to the same residue class modulo $m$

Then, a specific case comes by.

$59 ≡ -1 \pmod{60}$

Here my understanding breaks down. They both clearly belong to the same class (the numbers being "behind" one of $60$ as multuple, intuitively speaking). However, dividing $x$ and $y$ by $m$ the remainder is the same (Ruohonen) is no longer true, since $59 % 60 = 59$, and $-1 % 60 = -1$.

What am I missing?

$\endgroup$
6
  • 6
    $\begingroup$ A clearer definition is that $x\equiv y\pmod{n}$ iff $x - y$ is divisible by $n$. $\endgroup$ Commented Dec 30, 2017 at 5:52
  • 4
    $\begingroup$ Math generally defines the remainder as non-negative. That's unlike the C % modulo operator, whose behavior is implementation defined and can be negative, as you just found out. $\endgroup$ Commented Dec 30, 2017 at 6:18
  • 1
    $\begingroup$ For the purposes of defining a residue class $-1$ and $59$ fall in the same class modulo $60$, which is what Ruohonen is saying. The lesson is rather that the binary mod, or the C-notation a % b is not a foolproof test here. See my comment zipirovich's answer for more. The definition described by anomaly is the usual one (though yet another version is easier to generalize to other rings). $\endgroup$ Commented Dec 30, 2017 at 8:00
  • $\begingroup$ "yet another version is easier" <-- which other one? $\endgroup$ Commented Dec 30, 2017 at 9:09
  • $\begingroup$ FWIW, in Python a % b always has the same sign as b. $\endgroup$ Commented Dec 30, 2017 at 14:10

2 Answers 2

Reset to default
10
$\begingroup$

You're misinterpreting the mathematical definition of division with remainder when it's extended to negative integers. Your statement -1 % 60 = -1 is NOT true.

Quoting from the Wikipedia article on Remainder:

If $a$ and $d$ are integers, with $d$ non-zero, it can be proven that there exist unique integers $q$ and $r$, such that $a=qd+r$ and $0\le r<|d|$. The number $q$ is called the quotient, while $r$ is called the remainder.

Note that by definition, the remainder can NOT be negative. That's one reason why your example is wrong: the remainder can't be "$-1$".

Here's one way to look at it (somewhat informally). For example, you said that $20$ has a remainder of $2$ when divided by $3$. Yes, that's true, but why? I bet you were taught to look for the largest multiple of $3$ that doesn't exceed $20$. This is going to be $18$, and then the remainder is $20-18=2$.

Well, all you gotta do now is apply exactly the same logic to negative numbers too! Let's find the remainder of $-20$ modulo $3$. What is the largest multiple of $3$ that doesn't exceed $-20$? It is NOT $-18$, because $-18>-20$, not less. Instead, the largest multiple of $3$ that doesn't exceed $-20$ is $-21$, and the remainder is $(-20)-(-21)=1$.

In terms of the definition, $a=\color{blue}{q}d+\color{red}{r}$, where $\color{blue}{q}$ is the quotient and $\color{red}{r}$ is the remainder, $0\le\color{red}{r}<|d|$, for these two examples we have: $20=\color{blue}{6}\cdot3+\color{red}{2}$ for the first one, and $-20=\color{blue}{(-7)}\cdot3+\color{red}{1}$ for the second one.

Same for your last example. What is the largest multiple of $60$ that doesn't exceed $-1$? It is NOT $0$, because $0>-1$, not less. Instead, the largest multiple of $60$ that doesn't exceed $-1$ is $-60$, and the remainder is $(-1)-(-60)=59$. In terms of the definition: $-1=\color{blue}{(-1)}\cdot60+\color{red}{59}$.

$\endgroup$
7
  • 5
    $\begingroup$ Actually many programming languages (and processors) calculate the remainder exactly like this -1 % 60 =-1. This is a consequence of the more compelling "laws" (-m) DIV n = - (m DIV n) and m= n*(m DIV n)+(m%n) that they want to hold for all integers $m,n$, $n\neq0$. I would rather say that the problem in the computer approach is to think of MOD, or %, as an operation with numerical values rather than as a comparison operator with a true/false value (which is what a congruence is). Once the students figure out this, they can usually make progress. $\endgroup$ Commented Dec 30, 2017 at 7:49
  • 4
    $\begingroup$ Confession: In my time I have created interesting bugs when not knowing that computers think that a remainder is negative in some cases. Not too difficult to debug actually, but a WTF-moment nevertheless :-) $\endgroup$ Commented Dec 30, 2017 at 7:52
  • 1
    $\begingroup$ So, really, it boils down to "programming language have this one wrong"...? I understand intuitively why they belong to the same class. But really, the remainder must always be a positive integer, and... well, in programming languages, it's not! No wonder my brain wrestled this one to death... $\endgroup$ Commented Dec 30, 2017 at 9:14
  • $\begingroup$ I also just figured out a bug in a piece of software from years ago, just with this piece of info. It was actually a test I took for Toptal -- which I FAILED because of this very problem. $\endgroup$ Commented Dec 30, 2017 at 9:15
  • $\begingroup$ Amazing, I managed to rake 5 upvotes with my very first question here. If I had done that on StackOverflow, I would be a rockstar now! :D $\endgroup$ Commented Dec 30, 2017 at 9:18
9
$\begingroup$

Note that when dividing a number by $60$ the remainder should be an integer $r$ were $0 \leq r < 60$. The division algorithm tells us such an integer always exists in this range. Observe that $$59 = (0)\cdot 60 + 59$$ and $$-1 = (-1)\cdot 60 + 59 $$

So we see that $59 \equiv -1 \ (\operatorname{mod} 60)$. Both have a remainder of $59$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.