Large Integer Computing - Introduction to Cryptography with Java Applets - page 48

Here is another example for you:

80297
-3
300
-10000
90000
123 ) 9876543
-11070000
-1193457
--1230000
36543
-36900
-357
--369
12

It is entirely possible that this process could yield a negative remainder, as in the following
example (the absolute value of 542 is less than the divisor, 982).

10
982 ) 9278
-9820
-542

When this happens, it is easy to fix: simply add the divisor to the negative remainder and
subtract 1 from the quotient. In this case, this yields:

quotient = 9
remainder = 440.

Now we consider what to do when either the dividend or divisor is negative. Note that

if x is the positive dividend, y is the positive divisor, q is the quotient, and r is the remain-

der, we can express their relationship to each other as:

x = yq + rb> r ≥ 0.

changes sign, we can maintain this relationship by inverting some signs.
For example, we can perform calculations with all positive numbers, because:

If either x or y

if y is negative, change the sign of q , since

x = yq + r iff

x =

y

(

q

) + r ,