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
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.
No comments:
Post a Comment