Recursion - Data Structures and Problem Solving Using Java - page 312

remainder of a division by 10, the possible results range from 0 to 9. 3 This

range makes operator% useful for generating small integers.
If two numbers A and B give the same remainder when divided by N, we
say that they are congruent modulo N, written as A ≡ B (mod N ). In this case,
it must be true that N divides A - B . Furthermore, the converse is true: If N
divides A - B, then A ≡ B (mod N ). Because there are only N possible remain-
ders—0, 1, ..., N - 1— we say that the integers are divided into congruence
classes modulo N . In other words, every integer can be placed in one of N
classes, and those in the same class are congruent to each other, modulo N .
We use three important theorems in our algorithms (we leave the proof of
these facts as Exercise 7.10).

1. If A ≡ B (mod N ), then for any C, A + C ≡ B + C (mod N ).

2. If A ≡ B (mod N ), then for any D, AD ≡ BD (mod N ).

If A ≡ B (mod N ), then for any positive P, A P

≡ B P (mod N ).

3.

These theorems allow certain calculations to be done with less effort. For
instance, suppose that we want to know the last digit in 3333 5555 . Because
this number has more than 15,000 digits, it is expensive to compute the
answer directly. However, what we want is to determine 3333 5555 (mod 10).
As 3333 ≡ 3(mod 10), we need only to compute 3 5555 (mod 10). As 3 4 = 81,

we know that 3 4

≡ 1(mod 10), and raising both sides to the power of 1388 tells

us that 3 5552 1(mod 10). If we multiply both sides by 3 3

≡

= 27, we obtain

3 5555

≡ 27 ≡ 7(mod 10), thereby completing the calculation.

7.4.2 modular exponentiation
In this section we show how to compute X N (mod P ) efficiently. We can do so
by initializing result to 1 and then repeatedly multiplying result by X, apply-
ing the % operator after every multiplication. Using operator% in this way
instead of just the last multiplication makes each multiplication easier
because it keeps result smaller.
After N multiplications, result is the answer that we are looking for.
However, doing N multiplications is impractical if N is a 100-digit BigInteger .
In fact, if N is 1,000,000,000, it is impractical on all but the fastest machines.
A faster algorithm is based on the following observation. That is, if N is
even, then

X N = ( XX ⋅ )

N 2 ⁄

3. If n is negative, n%10 ranges from 0 to -9.