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

Thus and is a solution to . We
code this observation directly as fullGcd in Figure 7.18. The method inverse just
calls fullGcd , where X and Y are static class variables. The only detail left is that
the value given for X may be negative. If it is, line 35 of inverse will make it pos-
itive. We leave a proof of that fact for you to do as Exercise 7.14. The proof can
be done by induction.

X 1 = Y 1 AB = - ⁄ Y 1 AX BY + = 1

figure 7.18
A routine for
determining
multiplicative inverse

// Internal variables for fullGcd 1

private static long x; 2

private static long y; 3

4
5 /**
6 * Works back through Euclid's algorithm to find
7 * x and y such that if gcd(a,b) = 1,
8 * ax + by = 1.
9 */
10 private static void fullGcd( long a, long b )
11 {
12 long x1, y1;
13
14 if( b == 0 )
15 {
16 x = 1;
17 y = 0;
18 }
19 else
20 {
21 fullGcd( b, a % b );
22 x1 = x; y1 = y;
23 x = y1;
24 y = x1 - ( a / b ) * y1;
25 }
26 }
27
28 /**
29 * Solve ax == 1 (mod n), assuming gcd( a, n ) = 1.
30 * @return x.
31 */
32 public static long inverse( long a, long n )
33 {
34 fullGcd( a, n );
35 return x > 0 ? x : x + n;
36 }