# Why is $-145 \mod 63 = 44$?

When I enter $-145 \mod 63$ into google and some other calculators, I get $44$. But when I try to calculate it by hand I get that $-145/63$ is $-2$ with a remainder of $-19$. This makes sense to me, because $63\cdot (-2) = -126$, and $-126 - 19 = -145$.

So why do the calculators give that the answer is $44$?

• Why does 63 have to subtract 19? – Winston Nguyễn Dec 17 '15 at 17:30
• You might want to look at the related question, Why do we use “congruent to” instead of equal to? – Scott Dec 17 '15 at 17:41
• You might notice that $63-19=44$, which doesn't explain it, but is kind of a clue. There is a relationship between $-19$ and $44$ with respect to $63$. – Todd Wilcox Dec 17 '15 at 20:28
• Outside of mathematics, different computer programming languages with a modulo operator (usually spelled % in the C language family) handle mod of negatives in different ways, by the way, but in my experience as a programmer I almost always want the positive result, i.e. 44 instead of -19. – Russell Borogove Dec 17 '15 at 21:18

I think you have to start with the more basic question, "What does $\text{mod}$ mean?"

When we say "$\pmod{63}$" what we really mean is: Pretend that the "number line" is bent around in a circle so that when counting up, after you hit $62$ you return to $0$. On such a "number circle", the numbers $5,68, 131, 194, \dots$ are all equal to each other. And you can count downwards, too: $68, 5, -58, -121, \dots$ are also all equal.

It's common to interpret $a \pmod{63}$ to mean "Find the number between $0$ and $62$ that is equal to $a$, mod $63$." You can always find such a number by repeatedly adding or subtracting 63 to your given number until you get it into the desired range.

In this case, $-145 = -82 = -19 = 44 = 107 = \dots$. The only result that lies between $0$ and $62$ is $44$.

Note, though, that you are not wrong in thinking that $-145 \pmod{63} = -19$. When working mod $63$, the numbers $-19$ and $44$ are identical.

• All the answers were good but this one was the most clear, thank you. – Winston Nguyễn Dec 17 '15 at 17:58

Positive $145$ divided by $63$ is $2$ with a remainder of $19$, since $145=(2)63+19$.

However, $-145$ divided by $63$ is $-3$ with a remainder of $44$, since $-145=(-3)63+44$.

Remainders need to be positive. When dividing by $63$, they are between $0$ and $62$ inclusive.

• How does one get that -3 number. In normal division you have to try to find a number to multiply the divisor to get it as close to the dividend as possible without going over so i am confused? – Winston Nguyễn Dec 17 '15 at 17:43
• @WinstonNguyễn $-2$ does go over. $(-2)63>-145$ (since $(-2)63=-126$ and $-126>-145$). $-3$ is the largest integer that doesn't go over. – Akiva Weinberger Dec 17 '15 at 17:47
• Remember that the inequalities are backwards for negative numbers: $0>-1>-2>-3>\dotsb$. – Akiva Weinberger Dec 17 '15 at 17:48

We say $a \equiv b$ (mod n) if $a-b$ is a multiple of $n$. So notice that:

$$-145-44 = -189 = -3(63)$$

a=b (mod c) iff c|(a-b)

Some calculations using modular arithmetic: $$-145\equiv_{63}-145+63\cdot3\equiv_{63}-145+189\equiv_{63}44\equiv_{63}44-63\equiv_{63}-19$$

-19 = -145 mod 63.

44 = -145 mod 63.

107 = - 145 mod 63.

56550671 = -145 mod 63.

There are an infinite number of correct answers. Any number of the form: n = 63k - 145 will be a valid answer.

So why does your calculator choose 44 rather than -19 or 5650671? Probably because it was programmed to find the smallest non-negative value. Probably. Some programs are programmed differently and would give -19.