8.6. Arithmetic with a Prime Modulus 205
The sole exception is that 0 does not have an inverse. On the other hand, over the
integers, only 1 and -1 have inverses.
Surprisingly, when we’re workingmodulo a prime number,everynumber that
is not congruent to 0 has a multiplicative inverse. For example, if we’re working
modulo 5, then 3 is a multiplicative inverse of 7, since:
7 3 1 .mod5/(All numbers congruent to 3 modulo 5 are also multiplicative inverses of 7; for
example, 7 8 1 .mod5/as well.) The only exception is that numbers congruent
to 0 modulo 5 (that is, the multiples of 5) do not have inverses, much as 0 does not
have an inverse over the real numbers. Let’s prove this.
Lemma 8.6.1.Ifpis prime andkis not a multiple ofp, thenkhas a multiplicative
inverse modulop.
Proof. Sincepis prime, it has only two divisors: 1 andp. And sincekis not a mul-
tiple ofp, we must have gcd.p;k/D 1. Therefore, there is a linear combination of
pandkequal to 1:
spCtkD1;
and therefore
spCtk1 .modp/:
Butp0 .modp/, so
tk 0 CtkspCtk1 .modp/:Thus,tis a multiplicative inverse ofk.
Multiplicative inverses are the key to decryption in Turing’s code. Specifically,
we can recover the original message by multiplying the encoded message by the
inverseof the key:
mk ^1 Drem.mk;p/k ^1 (the def. (8.7) ofm)
.mk/k ^1 .modp/ (by Cor. 8.5.3)
m .modp/:
This shows thatmk ^1 is congruent to the original messagem. Sincemwas in
Œ0;p/, we can recover it exactly by taking a remainder:
mDrem.mk ^1 ;p/:So all we need to decrypt the message is to find a value ofk ^1. From the proof of
Lemma 8.6.1, we know thattis such a value, wherespCtkD 1. Findingtis easy
using the Pulverizer.