9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why does 63 have to subtract 19? $\endgroup$ – Winston Nguyễn Dec 17 '15 at 17:30
  • $\begingroup$ You might want to look at the related question, Why do we use “congruent to” instead of equal to? $\endgroup$ – Scott Dec 17 '15 at 17:41
  • $\begingroup$ 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$. $\endgroup$ – Todd Wilcox Dec 17 '15 at 20:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Russell Borogove Dec 17 '15 at 21:18
20
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Winston Nguyễn Dec 17 '15 at 17:43
  • 2
    $\begingroup$ @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. $\endgroup$ – Akiva Weinberger Dec 17 '15 at 17:47
  • $\begingroup$ Remember that the inequalities are backwards for negative numbers: $0>-1>-2>-3>\dotsb$. $\endgroup$ – Akiva Weinberger Dec 17 '15 at 17:48
6
$\begingroup$

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

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

$\endgroup$
1
$\begingroup$

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

In your case 63|(-145-44)

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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