8.7. Arithmetic with an Arbitrary Modulus 211
have, but rather modulo the product oftwolarge primes. Thus, we’ll need to know a
bit about how arithmetic works modulo a composite number in order to understand
RSA. Arithmetic modulo an arbitrary positive integer is really only a little more
painful than working modulo a prime—though you may think this is like the doctor
saying, “This is only going to hurt a little,” before he jams a big needle in your arm.
8.7.1 Relative Primality
Integers that have no prime factor in common are calledrelatively prime. This is
the same as having no common divisor (prime or not) greater than 1. It is also
equivalent to saying gcd.a;b/D 1.
For example, 8 and 15 are relatively prime, since gcd.8;15/D 1. Note that,
except for multiples ofp, every integer is relatively prime to a prime numberp.
Next we’ll need to generalize what we know about arithmetic modulo a prime
to work modulo an arbitrary positive integern. The basic theme is that arithmetic
modulonmay be complicated, but the integersrelatively primetonkeep the nice
properties of having inverses and being cancellable. For example,
Lemma 8.7.1. Letnbe a positive integer. Ifkisrelatively primeton, then there
exists an integerk ^1 such that:
kk ^1 1 .modn/:An inverse for anykrelatively prime tonis simply the coefficient ofkin the
linear combination ofkandnthat equals 1, exactly as in the proof of Lemma 8.6.1.
As a consequence of this lemma, we can cancel a multiplicative term from both
sides of a congruence if that term is relatively prime to the modulus:
Corollary 8.7.2.Supposenis a positive integer andkis relatively prime ton.
Then
akbk .modn/ implies ab .modn/:
This holds because we can multiply both sides of the first congruence byk ^1
and simplify to obtain the second.
The following lemma is a simple generalization of Corollary 8.6.3 with much
the same proof.
Lemma 8.7.3.Supposenis a positive integer andkis relatively prime ton. Let
k 1 ;:::;krbe all the integers in the intervalŒ1;n/that are relatively prime ton.
Then the sequence of remainders on division bynof:
k 1 k; k 2 k; k 3 k;:::; krk