Modular congruence not adding up

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?

Solution 1:

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}$.

Solution 2:

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