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
    $\begingroup$ A clearer definition is that $x\equiv y\pmod{n}$ iff $x - y$ is divisible by $n$. $\endgroup$ – anomaly Dec 30 '17 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$ – dxiv Dec 30 '17 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$ – Jyrki Lahtonen Dec 30 '17 at 8:00
  • $\begingroup$ "yet another version is easier" <-- which other one? $\endgroup$ – Merc Dec 30 '17 at 9:09
  • $\begingroup$ FWIW, in Python a % b always has the same sign as b. $\endgroup$ – PM 2Ring Dec 30 '17 at 14:10
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$
  • 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$ – Jyrki Lahtonen Dec 30 '17 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$ – Jyrki Lahtonen Dec 30 '17 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$ – Merc Dec 30 '17 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$ – Merc Dec 30 '17 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$ – Merc Dec 30 '17 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$

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.