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$
    – anomaly
    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$
    – dxiv
    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$ Dec 30, 2017 at 8:00
  • $\begingroup$ "yet another version is easier" <-- which other one? $\endgroup$
    – Merc
    Dec 30, 2017 at 9:09
  • $\begingroup$ FWIW, in Python a % b always has the same sign as b. $\endgroup$
    – PM 2Ring
    Dec 30, 2017 at 14:10

2 Answers 2

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$ 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$ 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$
    – Merc
    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$
    – Merc
    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$
    – Merc
    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.

Not the answer you're looking for? Browse other questions tagged .