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

The gcd algorithm is used implicitly to solve a similar mathematical prob-
lem. The solution 1

The greatest com-
mon divisor and
multiplicative
inverse can also be
calculated in loga-
rithmic time by
using a variant of
Euclid's algorithm.

1(mod N ) is called the multi-
plicative inverse of A, mod N . Also assume that 1

≤ X < N to the equation AX ≡

A < N . For example, the
inverse of 3, mod 13 is 9; that is, 3 ⋅ 9 mod 13 yields 1.
The ability to compute multiplicative inverses is important because equa-
tions such as 3 i ≡ 7(mod 13) are easily solved if we know the multiplicative
inverse. These equations arise in many applications, including the encryption
algorithm discussed at the end of this section. In this example, if we multiply
by the inverse of 3 (namely 9), we obtain i ≡ 63(mod 13), so i = 11 is a solu-
tion. If

≤

AX ≡ 1(mod N ), then AX + NY = 1(mod N )

is true for any Y . For some Y , the left-hand side must be exactly 1. Thus the
equation

AX + NY = 1

is solvable if and only if A has a multiplicative inverse.
Given A and B, we show how to find X and Y satisfying

AX + BY = 1

We assume that 0 ≤ ⎥ B ⎪ < ⎥ A ⎪ and then extend the gcd algorithm to compute

X and Y .
First, we consider the base case, B ≡ 0. In this case we have to solve AX = 1,
which implies that both A and X are 1. In fact, if A is not 1, there is no multiplica-
tive inverse. Hence A has a multiplicative inverse modulo N only if gcd( A, N ) = 1.
Otherwise, B is not zero. Recall that gcd( A, B ) ≡ gcd( B, A mod B ). So we
let A = BQ + R . Here Q is the quotient and R is the remainder, and thus the
recursive call is gcd( B, R ). Suppose that we can recursively solve

BX 1 RY 1 + = 1

Since RABQ = - , we have

BX 1 ABQ + ( - ) Y 1 = 1

which means that

AY 1 BX 1 QY 1 + ( - ) = 1