5
$\begingroup$

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

  • 0
    Are you asking why $x = -109$ is a solution for the congruence?2011-07-26
  • 0
    Negative voter?2011-07-26
  • 0
    @DJC:No,that is trivial,but how to effectively write $-109$ to that form.2011-07-26
  • 0
    How to find the remainder? Divide 109 by 60; it's $1$ and change. So $109 = 60(1) + 49$ (figure out the $49$ directly; it's easy). Multiplying all by $-1$ you get $-109 = (-1)60 - 49$. Add $60-60$ to the right hand side to get a positive remainder: $-109 = (-2)60 + (60-49) = (-2)60 + 11$. This shows $-109\equiv 11\pmod{60}$. This follows the proof of the division algorithm for negative dividends, after you have established it for positive ones.2011-07-26
  • 1
    @Tretwick: "$a\equiv\mod b$" is a nonsensical string of mathematical symbols.2011-07-26
  • 0
    @Tretwick: Integer division is reasonably quick; computationally speaking, for instance, finding the gcd of two numbers by repeated integer-division-with-reminder is considered a "fast algorithm".2011-07-26
  • 0
    I don't understand why people are so harsh here.2011-07-27
  • 0
    @Theo: Look at the title. What does it mean to write something in the form "$a\equiv\mod b$"? What does "$a\equiv \mod b$" mean?2011-07-27
  • 0
    @Theo: I didn't downvote the question, so don't look at me for the -2. In fact, the -2 was there before I posted that comment.2011-07-27
  • 0
    @ Arturo Magidin :It's very late in here,and I was in the process of editing the question.2011-07-27
  • 0
    @Tretwick: "Here the numbers are quite large." Actually, they are pretty small by today's standards (less than 16 bits to encode the largest). And you want to do division; it's really quite simple. Dividing $19177$ by $4900$ is *not hard*. In fact, you can easily estimate to get a first approximation: it's somewhere between $3$ and $4$ (just note that $4900$ is close to $5000$ and $19177$ is close to $20000$; even if you are off, doing that first approximation will get you a much simpler division to do later). $4900\times -4 = -19600$, and $-19177-(-19600) = 423$ and you're done. Easy!2011-07-27
  • 0
    @Theo: No offense taken.2011-07-27
  • 0
    My apologies to all for the inconveniences,I don't really mind negative votes as long I am getting usefull feedback from the community :-)2011-07-27
  • 1
    Maybe you should be a little bit more precise. You want $x \equiv a \pmod b$ with $0 \leq a \lt b$.2011-07-27
  • 0
    @Theo Buehler:Check it now :-)2011-07-27

5 Answers 5

7

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.

  • 0
    Thanks for the answer. :-)2011-07-27
4

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

2

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.

1

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

1

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