Discrete Mathematics: Elementary and Beyond

6.8 Strange Numbers 113

Division.Next, we want to divide the equation by 5. This is what we
discussed above: We have to use the Euclidean Algorithm. The computation
of the greatest common divisor is easy:

gcd(127,5) = gcd(2,5) = gcd(2,1) = 1.

This does not give anything new: We knew in advance that this greatest
common divisor will be 1. To get more, we have to follow this computation
by another one, where each number is written as an integer multiple of 127
plus an integer multiple of 5:

gcd(127,5) = gcd(127− 25 · 5 ,5) = gcd(127− 25 · 5 ,(−2)·127+51·5) = 1.

This gives that
(−2)·127+51·5=1.

Thus 5· 51 ≡1 (mod 127), and so we have found the “reciprocal” of 5
modulo 127.
Instead of dividing equation (6.4) by five, we multiply by its “reciprocal,”
51, to get
y≡ 51 ·118 (mod 127). (6.6)

Conclusion.If we evaluate the right-hand side of (6.6) and then compute
its remainder modulo 127, we get thaty≡49 (mod 127), or in other words,
Y=49 is the solution. To getx, we have to substitute this value back into
one of the original equations:

2 x+89· 49 ≡23 (mod 127),

whence
2 x≡ 23 − 89 · 49 ≡107 (mod 127).

So we have to do one more division. In analogy with what we did above,
we get
(−63)·2+127=1,

and hence
64 · 2 ≡1 (mod 127).

So instead of dividing by 2, we can multiply by 64, to get

x≡ 64 ·107 (mod 127).

Computing the right-hand side and its remainder modulo 127, we get that
x≡117 (mod 127), or in other words,X=117. Thus we have solved (6.4).

Example 3.We can even solve some quadratic equations; for example,

x^2 − 3 x+2≡0 (mod 53).