Mathematics for Computer Science

Chapter 8 Number Theory206

8.6.2 Cancellation

Another sense in which real numbers are nice is that one can cancel multiplicative
terms. In other words, if we know thatm 1 kDm 2 k, then we can cancel thek’s
and conclude thatm 1 Dm 2 , providedk¤ 0. In general, cancellation isnotvalid
in modular arithmetic. For example,

2 
 3  4 
3 .mod6/;

but canceling the 3’s leads to thefalseconclusion that 2 4 .mod6/. The fact
that multiplicative terms cannot be canceled is the most significant sense in which
congruences differ from ordinary equations. However, this difference goes away if
we’re working modulo aprime; then cancellation is valid.

Lemma 8.6.2.Supposepis a prime andkis not a multiple ofp. Then

akbk .modp/ IMPLIES ab .modp/:

Proof. Multiply both sides of the congruence byk^1. 

We can use this lemma to get a bit more insight into how Turing’s code works.
In particular, the encryption operation in Turing’s codepermutes the set of possible
messages. This is stated more precisely in the following corollary.

Corollary 8.6.3. Supposepis a prime andkis not a multiple ofp. Then the
sequence of remainders on division bypof the sequence:

1 
k; 2
k; :::; .p1/
k

is a permutation^5 of the sequence:

1; 2; :::; .p1/:

Proof. The sequence of remainders containsp 1 numbers. Sincei
kis not
divisible bypforiD1;:::p 1 , all these remainders are inŒ1;p/by the definition
of remainder. Furthermore, the remainders are all different: no two numbers in
Œ1;p/are congruent modulop, and by Lemma 8.6.2,i
k j
k .modp/if
and only ifij .modp/. Thus, the sequence of remainders must containallof
Œ1;p/in some order. 

(^5) Apermutationof a sequence of elements is a reordering of the elements.