A "fast" way for writing negative number (say $x$) as $x \equiv a \pmod b$ with $0 \leq a \lt b$

Question

Which is the best method for writing negative numbers in the form of $a \bmod b$? (where $a$ and $b$ are positive integers)

While using Chinese remainder theorem to compute the solution of these linear congruences, $$\begin{align}x &\equiv 2 \pmod 3 \\ x &\equiv 3 \pmod 4 \\ x &\equiv 1 \pmod 5\end{align}$$ as the solution I got $x = -109$, now I need to represent this result in the form of $a \bmod b$,where $b=60$ (here),this case is very easy as the numbers are very small.

In this one I keep checking multiples of $60$ repeatedly and then add $-109$ to the first one $109$, in this case $2\cdot 60 = 120$ and then adding $-109$ we get $11$,now we can write $-109 \equiv 11 \bmod 60$... but is this is the only way? since if the number is large, checking the multiples could be time consuming.

For example here, the number is $-19177$ which needs to expressed in the form $a \bmod 4900$, how to manually and quickly find "$a$" in such cases (assume numbers up-to $6$ digits).

Answer 1

If you are uncomfortable dividing the negative number $-109$ by $60$, do this:

(i) Divide $109$ by $60$. The remainder is $49$.

(ii) Your answer is $60-49$.

This procedure almost always works. The only time it doesn't is when the remainder on dividing your positive number is $0$. Then the answer for the negative number should also be $0$.

Example: Find the remainder when $-2011$ is divided by $60$.

(i) Divide $2011$ by $60$. The remainder is $31$.

(ii) The remainder when $-2011$ is divided by $60$ is therefore $60-31$, that is, $29$.

Let's check: $-2011=(60)(-34)+29$.

Note: We are here finding the remainder when a negative number is divided by a positive one. Of course, if you are interested in dividing $-2011$ by $-60$, just change both signs, and proceed "normally."

Exercise: Prove that the above procedure is correct. (It really is not hard.)

Calculating Remainers: Suppose that $a$ and $m$ are positive, and not too large. We want the remainder when $a$ is divided by $m$. For example, let $a=4000000$ and $m=2011$.

(a) Divide on the calculator. My calculator display shows $1989.0602$. (The calculator knows a couple of additional digits but is keeping them hidden.)

(b) Immediately subtract the integer part of the answer, that is, $1989$. Do not copy down any number and rekey. If necessary, use the calculator "memory" feature. I got $0.0601691$. Notice that the calculator has just revealed some digits it had kept hidden. The last digit is not trustworthy.

(c) Immediately multiply by $m$. I got $121.00006$.

(d) Find the nearest integer to the result in (c). If calculators were always absolutely exact, the number in (c) would be an integer. The inexactness is due to roundoff error. That error is small, and finding the nearest integer eliminates the error. Often, with smallish $a$, step (d) will be unnecessary, because the result of step (c), on the display, will look like an integer.

(e) We conclude that our remainder is $121$. The whole calculation takes a few seconds, mostly spent keying in the original numbers.

On a scientific calculator, the procedure should be reliable up to at least $a=10^7$. It even works nicely on a primitive "grocery store" calculator.

If $a$ is quite large, say $10^{13}$ or beyond, this calculator procedure breaks down. We cannot even input all the digits of $a$ into the calculator! However, there are many calculator programs available, several of them free, which calculate to greater precision, or even "infinite" precision.

Answer 2

To answer your question: you divide and you conquer.

Do integer division! It's really very straightforward, even by hand, even with large numbers. You can get a good estimate easily enough, and go from there in the worst of cases.

First, to find the remainder of $a$ modulo $b$ when $a$ is positive, just divide $a$ by $b$.

To pick a random example I am now making up, suppose you want to find the remainder $a=5,831,273$ modulo $b=3,871$.

Clearly, $1000\lt \frac{a}{b} \lt 2000$; it's closer to $2000$ and to $1000$; multiplying $3871\times 1500$ for a first a first approximation, we get $5,806,500$, which is pretty close. Then $a\equiv a-5806500 = 24,773 \pmod{b}$, which is still too large. Now we divide $24,773$ by $3871$: it's somewhere between $6$ and $8$ ($3871$ is between $3000$ and $4000$, $24,773$ is a bit more than $24,000$; this is like estimating $24$ divided by $3$ or $4$). Trying $7$, we have $3871\times 7 = 27097$, too much; now we have $a\equiv 24,773 \equiv 24,773 - 27097 = -2324\pmod{b}$. One more step does it: add $3871$ to get $a\equiv 1547 \pmod{b}$. This was doing it by hand; with a simple calculator at hand, I would simly compute $\frac{a}{b}\approx 1506.4$ to figure out that I need to compute $a - 1506b$ to get the remainder.

If $a$ is negative, then do the same thing for $-a$; once you know that $-a\equiv c \pmod{b}$ with $0\leq c \lt |b|$, then $a\equiv -c \equiv |b|-c\pmod{b}$ and you are done, just one step more than for positive $a$.

Answer 3

In simplest terms, the way you show that $-109 \equiv 11 \pmod{60}$ is to add $60$ to $-109$ repeatedly until you get a result which is non-negative; that result will be $-109 + 2 \cdot 60 = 11$.

Of course, in practice repeated addition would get tedious, so we use division and multiplication as a shortcut: divide $-109$ by $60$, and you get about $-1.8167$. Round that down, and you get $-2$. Multiply that by $60$ and subtract it from $-109$ to get $-109 - (-2 \cdot 60) = -109 + 2 \cdot 60 = 11$.

Of course, that the exact same thing as you'd do to reduce a large positive number modulo $60$, or indeed modulo any number. Just remember to always round downwards, whether the result of the division is positive or negative.

Answer 4

HINT $\rm\qquad\ A\equiv\: a\ \ \ \Rightarrow\ \ \: {-}A\equiv\: -a\:,\ \ $ and $\rm\:\ \ {-}a\ \equiv\ m-a\quad (mod\ m)$

Proof $\rm\ \ m\ |\ A-a\ \Rightarrow\ m\ |\: {-}A+a\:,\:$ and $\rm\ m\ |\: {-}a-(m-a)\: =\: -m $

E.g. $\rm\ mod\ 10:\ \: 103\ \equiv\ 3\:\ \Rightarrow\ {-}103\ \equiv\: -3\ \equiv\: 10-3\ \equiv\ 7\ \ (mod\ 10)$

Note also $\rm\ 0 < a < m\ \Rightarrow\ 0 < m-a < m\:,\:$ i.e. $\rm\ a\:$ reduced $\rm\:\Rightarrow\ m-a\ $ reduced $\rm\ (mod\ m)\:.$

Answer 5

In answer to the added question: the way you get the $11$ is by dividing $-109$ by $60$; $11$ is the remainder (the quotient is $-2$).