112 6. Integers, Divisors, and Primes
(we could replace−3 by its remainder 44 modulo 47 if we wanted to keep
numbers positive, but this is optional).
Next we have to find the reciprocal of 7 modulo 47. The Euclidean Al-
gorithm gives
gcd(7,47) = gcd(7,5) = gcd(2,5) = gcd(2,1) = 1,and following the extended version we get
5=47− 6 · 7 , 2=7−5=7−(47− 6 ·7) = 7· 7 − 47 ,1=5− 2 ·2 = (47− 6 ·7)− 2 ·(7· 7 −47) = 3· 47 − 20 · 7 ,which shows that (−20)· 7 ≡1 (mod 47). So the reciprocal of 7 modulo 47
is−20 (which again we could write as 27).
Now dividing both sides of (6.3) by 7, which is the same as multiplying
both sides by 27, we get
x≡13 (mod 47).(Here we get 13 either as the remainder of (−3)(−20), or as the remainder
of 44·27 modulo 47; the result is the same.)
Example 2.Next, let us solve a system of two linear equations, with two
variables. We’ll make the numbers a little bigger, to see that we can cope
with larger numbers too. Let the modulus bep= 127, and consider the
equations
12 X+ 31 Y= 2 , (6.4)
2 X+ 89 Y= 23.We can rewrite these as congruences:
12 x+31y≡ 2 (mod 127),
2 x+89y≡ 23 (mod 127).a. Eliminate a variable.How would we solve this system if these were
ordinary equations? We could multiply the second equation by 6 and sub-
tract it from the first, to eliminate thexterms. We can do this in this
prime field as well, and get
(31− 6 ·89)y≡ 2 − 6 ·23 (mod 127),or
(−503)y≡−136 (mod 127).
We can replace these negative numbers by their remainders modulo 127 to
get
5 y≡118 (mod 127). (6.5)