8.9: Multiplicative Inverses and Cancelling

The multiplicative inverse of a number \(x\) is another number \(x^{-1}\) such that

\[\nonumber x^{-1} \cdot x = 1\]

From now on, when we say “inverse,” we mean multiplicative (not relational) inverse.

For example, over the rational numbers, \(1/3\) is, of course, an inverse of 3, since,

\[\nonumber \frac{1}{3} \cdot 3 = 1.\]

In fact, with the sole exception of 0, every rational number \(n/m\) has an inverse, namely, \(m/n\). On the other hand, over the integers, only 1 and -1 have inverses. Over the ring \(\mathbb{Z}_n\), things get a little more complicated. For example, in \(\mathbb{Z}^{15}\), 2 is a multiplicative inverse of 8, since

\[\nonumber 2 \cdot 8 = 1 (\mathbb{Z}_{15}).\]

On the other hand, 3 does not have a multiplicative inverse in \(\mathbb{Z}_{15}\). We can prove this by contradiction: suppose there was an inverse \(j\) for 3, that is

\[\nonumber 1 = 3 \cdot j (\mathbb{Z}_{15}).\]

Then multiplying both sides of this equality by 5 leads directly to the contradiction \(5 = 0\):

\[\begin{aligned} 5 &= 5 \cdot (3 \cdot j) \\ &= (5 \cdot 3) \cdot j \\ &= 0 \cdot j = 0 (\mathbb{Z}_{15})\end{aligned}\]

So there can’t be any such inverse \(j\).

So some numbers have inverses modulo 15 and others don’t. This may seem a little unsettling at first, but there’s a simple explanation of what’s going on.

Relative Primality

Integers that have no prime factor in common are called relatively prime.¹⁰ This is the same as having no common divisor (prime or not) greater than 1. It’s also equivalent to saying \(\text{gcd}(a, b) = 1\).

For example, 8 and 15 are relatively prime, since \(\text{gcd}(8, 15) = 1\). On the other hand, 3 and 15 are not relatively prime, since \(\text{gcd}(3, 15) = 3 \neq 1\). This turns out to explain why 8 has an inverse over \(\mathbb{Z}_{15}\) and 3 does not.

Lemma 8.9.1. If \(k \in [0..n)\) is relatively prime to \(n\), then \(k\) has an inverse in \(\mathbb{Z}_{n}\).

Proof. If \(k\) is relatively prime to \(n\), then \(\text{gcd}(n, k) = 1\) by definition of gcd. This means we can use the Pulverizer from section 8.2.2 to find a linear combination of \(n\) and \(k\) equal to 1:

\[\nonumber sn + tk=1. \]

So applying the General Principle of Remainder Arithmetic (Lemma 8.7.1), we get

\[\nonumber \text{rem}(s, n) \cdot \text{rem}(n, n))+(\text{rem}(t, n) \cdot \text{rem}(k, n))=1 (\mathbb{Z}_n).\]

But \(\text{rem}(n, n)=0\), and \(\text{rem}(k, n)=k\) since \(k \in [0 . . n)\), so we get

\[\nonumber \text{rem}(t, n) \cdot k=1 (\mathbb{Z}_{n} ) \]

Thus, \(\text{rem}(t, n)\) is a multiplicative inverse of \(k. \quad \blacksquare\)

By the way, it's nice to know that when they exist, inverses are unique. That is,

Lemma 8.9.2. If \(i\) and \(j\) are both inverses of \(k\) in \(\mathbb{Z}_{n}\), then \(i=j\).

Proof.

\[\nonumber i=i \cdot 1=i \cdot(k \cdot j)=(i \cdot k) \cdot j=1 \cdot j=j(\mathbb{Z}_{n}). \quad \blacksquare\]

So the proof of Lemma 8.9.1 shows that for any \(k\) relatively prime to \(n\), the inverse of \(k\) in \(\mathbb{Z}_n\) is simply the remainder of a coefficient we can easily find using the Pulverizer.

Working with a prime modulus is attractive here because, like the rational and real numbers, when \(p\) is prime, every nonzero number has an inverse in \(\mathbb{Z}_p\). But arithmetic modulo a composite is really only a little more painful than working modulo a prime—though you may think this is like the doctor saying, “This is only going to hurt a little,” before he jams a big needle in your arm.

Cancellation

Another sense in which real numbers are nice is that it’s ok to cancel common factors. In other words, if we know that \(tr = ts\) for real numbers \(r, s, t\), then as long as \(t \neq 0\), we can cancel the \(t\)’s and conclude that \(r = s\). In general, cancellation is not valid in \(\mathbb{Z}_n\). For example,

\[\label{8.9.1} 3 \cdot 10 = 3 \cdot 5 (\mathbb{Z}_{15}), \]

but cancelling the 3’s leads to the absurd conclusion that 10 equals 5.

The fact that multiplicative terms cannot be cancelled is the most significant way in which \(\mathbb{Z}_n\) arithmetic differs from ordinary integer arithmetic.

Definition \(\PageIndex{3}\)

A number \(k\) is cancellable in \(\mathbb{Z}^{n}\) iff

\[\nonumber k \cdot a = k \cdot b \text{ implies } a = b (\mathbb{Z}_n)\]

for all \(a, b \in [0 .. n).\)

If a number is relatively prime to 15, it can be cancelled by multiplying by its inverse. So cancelling works for numbers that have inverses:

Lemma 8.9.4. If \(k\) has an inverse in \(\mathbb{Z}_n\), then it is cancellable.

But 3 is not relatively prime to 15, and that’s why it is not cancellable. More generally, if \(k\) is not relatively prime to \(n\), then we can show it isn’t cancellable in \(\mathbb{Z}_n\) in the same way we showed that 3 is not cancellable in (\ref{8.9.1}).

To summarize, we have

Theorem \(\PageIndex{5}\)

The following are equivalent for \(k \in [0..n)\):

\(\text{gcd}(k, n) = 1\),

\(k\) has an inverse in \(\mathbb{Z}_n\),

\(k\) is cancellable in \(\mathbb{Z}_n\).

Decrypting (Version 2.0)

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 \(\mathbb{Z}_n\)-inverse, \(j\), of the key:

\[\nonumber \hat{m} \cdot j = (m \cdot k) \cdot j = m \cdot (k \cdot j) = m \cdot 1 = m (\mathbb{Z}_n).\]

So all we need to decrypt the message is to find an inverse of the secret key \(k\), which will be easy using the Pulverizer—providing \(k\) has an inverse. But \(k\) is positive and less than the modulus \(n\), so one simple way to ensure that \(k\) is relatively prime to the modulus is to have \(n\) be a prime number.

Breaking Turing’s Code (Version 2.0)

The Germans didn’t bother to encrypt their weather reports with the highly-secure Enigma system. After all, so what if the Allies learned that there was rain off the south coast of Iceland? But amazingly, this practice provided the British with a critical edge in the Atlantic naval battle during 1941.

The problem was that some of those weather reports had originally been transmitted using Enigma from U-boats out in the Atlantic. Thus, the British obtained both unencrypted reports and the same reports encrypted with Enigma. By comparing the two, the British were able to determine which key the Germans were using that day and could read all other Enigma-encoded traffic. Today, this would be called a known-plaintext attack.

Let’s see how a known-plaintext attack would work against Turing’s code. Suppose that the Nazis know both the plain text, \(m\), and its encrypted form, \(\hat{m}\). Now in ersion 2.0,

\[\nonumber \hat{m} = m \cdot k (\mathbb{Z}_n).\]

and since \(m\) is positive and less than b the prime \(n\), the Nazis can use the Pulverizer to find the \(\mathbb{Z}_n)\)-inverse, \(j\), of \(m\). Now

\[\nonumber j \cdot \hat{m} = j \cdot (m \cdot k) = j \cdot (m \cdot k) = 1 \cdot k = k (\mathbb{Z}_n).\]

So by computing \(j \cdot \hat{m} = k (\mathbb{Z}_n)\), the Nazis get the secret key and can then decrypt any message!

This is a huge vulnerability b , so Turing’s hypothetical Version 2.0 code has no practical value. Fortunately, Turing got better at cryptography after devising this code; his subsequent deciphering of Enigma messages surely saved thousands of lives, if not the whole of Britain.

Turing Postscript

A few years after the war, Turing’s home was robbed. Detectives soon determined that a former homosexual lover of Turing’s had conspired in the robbery. So they arrested him—that is, they arrested Alan Turing—because at that time in Britain, homosexuality was a crime punishable by up to two years in prison. Turing was sentenced to a hormonal “treatment” for his homosexuality: he was given estrogen injections. He began to develop breasts.

Three years later, Alan Turing, the founder of computer science, was dead. His mother explained what happened in a biography of her own son. Despite her repeated warnings, Turing carried out chemistry experiments in his own home. Apparently, her worst fear was realized: by working with potassium cyanide while eating an apple, he poisoned himself.

However, Turing remained a puzzle to the very end. His mother was a devout woman who considered suicide a sin. And, other biographers have pointed out, Turing had previously discussed committing suicide by eating a poisoned apple. Evidently, Alan Turing, who founded computer science and saved his country, took his own life in the end, and in just such a way that his mother could believe it was an accident.

Turing’s last project before he disappeared from public view in 1939 involved the construction of an elaborate mechanical device to test a mathematical conjecture called the Riemann Hypothesis. This conjecture first appeared in a sketchy paper by Bernhard Riemann in 1859 and is now one of the most famous unsolved problems in mathematics.

 

¹⁰Other texts call them coprime.