3.2 Cancellation Another sense in which real number are nice is that one can cancel multiplicative terms In other words if we know that mik= m2k, then can cancel the k's and conclude that m1=m2, provided k+0. In general, cancellation is not valid in modular arithmetic. For example, this congruence is correct: 2.3≡4.3(mod6) But if we cancel the 3 s we reach a false conclusion: 2≡4(mod6) The fact that multiplicative terms can not be cancelled is the most significant sense in which congruences differ from ordinary equations. However, this difference goes away if were working modulo a prime; then cancellation is valid Lemma 4. Suppose p is a prime and k is not a multiple of p. Then ak≡bk(modp) Implies a≡b(modp) Proof. Multiply both sides of the congruence by k- 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 code permutes the space of messages. This is stated more precisely in the following corollary. Corollary 5. Suppose p is a prime and k is not a multiple of p. Then the sequence (0·k)remp,(1·k)remp,(2.k)remp, k) rem p is a permutation of the sequence 0,1,2,…,(p-1) This remains true if the first term is deleted from each sequence Proof. The first sequence contains p numbers, which are all in the range 0 to p-1 by the definition of remainder. Furthermore, the numbers in the first sequence are all different by part 2 of Lemma 2, mih rem p= m2k rem p if and only if mI m2(mod p), and no two numbers in the range 0, 1,.,p-1 are congruent modulo p. Thus, the first sequence must contain all of the numbers from 0 to p-1 in some order. The claim remains true if the first terms are deleted because both sequences begin with 0 For example, suppose p=5 and k= 3. Then the sequence 3)rem5,(1·3)rem5,(2.3)rem5,(3·3)rem5,(43)rem5 is a permutation of 0, 1, 2, 3, 4 and the last four terms are a permutation of 1, 2,3,4.As long as the Nazis don, t know the secret key ki, they don't know how the message space is permuted by the process of encryption and thus can t read encoded messages8 Number Theory II 3.2 Cancellation Another sense in which real number are nice is that one can cancel multiplicative terms. In other words, if we know that m1k = m2k, then can cancel the k’s and conclude that m1 = m2, provided k �= 0. In general, cancellation is not valid in modular arithmetic. For example, this congruence is correct: 2 3 · · ≡ 4 3 (mod 6) But if we cancel the 3’s, we reach a false conclusion: 2 ≡ 4 (mod 6) The fact that multiplicative terms can not be cancelled is the most significant sense in which congruences differ from ordinary equations. However, this difference goes away if we’re working modulo a prime; then cancellation is valid. Lemma 4. Suppose p is a prime and k is not a multiple of p. Then ak ≡ bk (mod p) implies a ≡ b (mod p) Proof. Multiply both sides of the congruence by k−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 code permutes the space of messages. This is stated more precisely in the following corollary. Corollary 5. Suppose p is a prime and k is not a multiple of p. Then the sequence: � � (0 · k) rem p, (1 · k) rem p, (2 · k) rem p, . . . , (p − 1) · k rem p is a permutation of the sequence: 0, 1, 2, . . . , (p − 1) This remains true if the first term is deleted from each sequence. Proof. The first sequence contains p numbers, which are all in the range 0 to p − 1 by the definition of remainder. Furthermore, the numbers in the first sequence are all different; by part 2 of Lemma 2, m1k rem p = m2k rem p if and only if m1 ≡ m2 (mod p), and no two numbers in the range 0, 1, . . . , p ­ 1 are congruent modulo p. Thus, the first sequence must contain all of the numbers from 0 to p − 1 in some order. The claim remains true if the first terms are deleted, because both sequences begin with 0. For example, suppose p = 5 and k = 3. Then the sequence: (0 � · 3) rem 5 �� � , (1 � · 3) rem 5 �� � , (2 � · 3) rem 5 �� � , (3 � · 3) rem 5 �� � , (4 � · 3) rem 5 �� � =0 =3 =1 =4 =2 is a permutation of 0, 1, 2, 3, 4 and the last four terms are a permutation of 1, 2, 3, 4. As long as the Nazis don’t know the secret key k, they don’t know how the message space is permuted by the process of encryption and thus can’t read encoded messages