6.8 Strange Numbers 111The key to solving this problem is the Euclidean Algorithm. Let us com-
pute the greatest common divisor ofaandp. This sounds silly, since we
know the answer right away:pis a prime and 1≤a<p, so they cannot
have any common divisor greater than 1, and so gcd(p, a) = 1. But re-
call that the Euclidean Algorithm gives more: it will provide the greatest
common divisor in the formau+pv, whereuadvare integers. Thus we
get
au+pv=1,
which implies that
au≡1 (modp).
We are almost done; the only problem is that the integerumay not be
between 1 andp−1. But ifxis the remainder ofumodulop, then mul-
tiplying the congruencex≡u(modp)bya(recall from Section 6.7 that
this is a legal operation on congruences), we get
ax≡au≡1 (modp),and since 0≤x≤p−1, this solves our problem.
Let us follow this algorithm on our example above, witha = 2 and
p= 234,527. The Euclidean Algorithm works really simply in this case:
Divide 234,527 by 2 with remainder, and the remainder is already down to
- This gives
2 ·(− 117 ,263) + 234, 527 ·1=1.
The remainder of -117,263 modulo 234,527 is 117,264, so we get that
1 /2= 117 , 264.6.8.4Compute 1 /53 modulo 234527.Once we know how to do basic arithmetic, more involved tasks like solv-
ing linear equations can be done by recalling what we would do with or-
dinary numbers. We illustrate this by some examples, where we use the
congruence notation along with its basic properties from Section 6.7.
Example 1.Consider a linear equation, say
7 X+3= 0 ,where the modulus is 47 (check in the table that this is a prime!). We can
rewrite this as a congruence:
7 x+3≡0 (mod 47).This second form is the more usual, so let’s work with this.
Just as we would do with an equation, we transform this as
7 x≡−3 (mod 47) (6.3)