Number Theory Il 3.1 Multiplicative Inverses The mutiplicative inverse of a number r is another number .- such that T·x Generally, multiplicative inverses exist over the real numbers. For example, the multi- plicative inverse of 3 is 1/3 since The sole exception is that o does not have an inverse On the other hand, inverses generally do not exist over the integers. For example, 7 can not be multiplied by another integer to give 1 Surprisingly, multiplicative inverses do exist when we re working modulo a prime num ber. For example, if were 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(mod 5)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 3. If p is prime and k is not a multiple of p, then k has a multiplicative inverse Proof. Since p is prime, it has only two divisors: 1 and p. And since k is not a multiple of p, we must have gcd(p, k)=l. Therefore, there is a linear combination of p and k equal to Rearranging terms gives the definition of congruence. Thus, t is a multiplicative inverse of This implies that p| 1-th by the definition of divisibility, and therefore by □ 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 inverse of the m.k=(mk rem p). k(mod p E mkk(mod p m(mod p) This shows that m*k- is congruent to the original message m. Since the m was in the p-l, we can recover it exactly taking a remainder m=m'k rem p So now we can decrypt!Number Theory II 7 3.1 Multiplicative Inverses The mutiplicative inverse of a number x is another number x−1 such that: x x−1 · = 1 Generally, multiplicative inverses exist over the real numbers. For example, the multi￾plicative inverse of 3 is 1/3 since: 1 3 = 1 · 3 The sole exception is that 0 does not have an inverse. On the other hand, inverses generally do not exist over the integers. For example, 7 can not be multiplied by another integer to give 1. Surprisingly, multiplicative inverses do exist when we’re working modulo a prime num￾ber. For example, if we’re working modulo 5, then 3 is a multiplicative inverse of 7, since: 7 3 · ≡ 1 (mod 5) (All numbers congruent to 3 modulo 5 are also multiplicative inverses of 7; for example, 7 8 · ≡ 1 (mod 5) 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 3. If p is prime and k is not a multiple of p, then k has a multiplicative inverse. Proof. Since p is prime, it has only two divisors: 1 and p. And since k is not a multiple of p, we must have gcd(p, k) = 1. Therefore, there is a linear combination of p and k equal to 1: sp + tk = 1 Rearranging terms gives: sp = 1 − tk This implies that p | 1 − tk by the definition of divisibility, and therefore tk ≡ 1 (mod p) by the definition of congruence. Thus, t is a multiplicative inverse of k. 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 inverse of the key: m∗ k−1 ≡ (mk rem p) k−1 · · (mod p) ≡ mkk−1 (mod p) ≡ m (mod p) This shows that m∗k−1 is congruent to the original message m. Since the m was in the range 0, 1, . . . , p − 1, we can recover it exactly taking a remainder: m = m∗ k−1 rem p So now we can decrypt!