8.5. Modular Arithmetic 201
The greatest common divisor of the two encrypted messages,m 1 andm 2 , is the
secret keyk. And, as we’ve seen, the GCD of two numbers can be computed very
efficiently. So after the second message is sent, the Nazis can recover the secret key
and readeverymessage!
A mathematician as brilliant as Turing is not likely to have overlooked such a
glaring problem, and we can guess that he had a slightly different system in mind,
one based onmodulararithmetic.
8.5 Modular Arithmetic
On the first page of his masterpiece on number theory,Disquisitiones Arithmeticae,
Gauss introduced the notion of “congruence”. Now, Gauss is another guy who
managed to cough up a half-decent idea every now and then, so let’s take a look
at this one. Gauss said thataiscongruenttobmoduloniffnj.a b/. This is
written
ab .modn/:
For example:
29 15 .mod7/ because 7 j.29 15/:
There is a close connection between congruences and remainders:
Lemma 8.5.1(Remainder).
ab .modn/ iff rem.a;n/Drem.b;n/:
Proof. By the Division Theorem 8.1.5, there exist unique pairs of integersq 1 ;r 1
andq 2 ;r 2 such that:
aDq 1 nCr 1
bDq 2 nCr 2 ;
wherer 1 ;r 22 Œ0;n/. Subtracting the second equation from the first gives:
a bD.q 1 q 2 /nC.r 1 r 2 /;
wherer 1 r 2 is in the interval. n;n/. Nowab .modn/if and only ifndivides
the left side of this equation. This is true if and only ifndivides the right side, which
holds if and only ifr 1 r 2 is a multiple ofn. Given the bounds onr 1 r 2 , this
happens precisely whenr 1 Dr 2 , that is, when rem.a;n/Drem.b;n/.
