We've come a long way, but there's still a bit more we can squeeze out of this. Up to now, we've been dealing with $\mathbb Z_p$ because of all the nice properties we get from it, but what if we really happen to want to work within $\mathbb Z_m$, where $m$ is not prime?
This sounds like playing with fire because, as we showed, we could get stuck when trying to solve our congruence since we may try to find an inverse for our element and there is none. However, we will show that if we can break up the modulus $m$ into relatively prime factors, then we are still able to find a solution.
That is, to solve $x \equiv a \pmod m$, if $m = m_1 \cdot m_2$ where $m_1$ and $m_2$ are relatively prime, then we can simply solve the simultaneous congruences \begin{align*} x &\equiv a \pmod{m_1} \\ x &\equiv a \pmod{m_2} \end{align*} instead and get our answer. The question then is how to solve simultaneous congruences under different moduli.
The origins of this problem are due to Sunzi, a Chinese mathematician from the third century AD and who happens to have the same name as the author of The Art of War but is not the same person. He first posed the following problem and theorem which solves it. \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*}
Let $a_1, a_2, \dots, a_k$ be integers and suppose that $m_1, m_2, \dots, m_k$ are $k$ pairwise positive relatively prime moduli. Then the system of equations \begin{align*} x & \equiv a_1 & \pmod{m_1} \\ x & \equiv a_2 & \pmod{m_2} \\ & \vdots \\ x & \equiv a_k & \pmod{m_k} \end{align*} has a unique solution modulo $m_1 \cdot m_2 \cdots m_k$.
Let $a_1, \dots, a_k$ be arbitrary integers and let $m_1, \dots, m_k$ be arbitrary positive integers with $\gcd(m_i, m_j) = 1$ for $1 \leq i \lt j \leq k$. Let $n = m_1 \cdot m_2 \cdots m_k$. For each $1 \leq i \leq k$, we define $n_i = \frac n {m_i}$. That is, $n_i$ is the product of the moduli except the $i$th one, $m_i$.
Here, we will rely on the following claim.
If $a$ and $b$ are relatively prime and $a$ and $c$ are relatively prime, then $a$ and $bc$ are relatively prime.
From this, we have that $m_i$ is relatively prime to $n_i$. Intuitively, this makes sense—$m_i$ is known to be relatively prime to the product of many numbers that are relatively prime with $m_i$.
First, we will consider a solution $x_i$ to the simultaneous congruences \begin{align*} x_i & \equiv 0 & \pmod{m_1} \\ x_i & \equiv 0 & \pmod{m_2} \\ & \vdots \\ x_i & \equiv 0 & \pmod{m_{i-1}} \\ x_i & \equiv 1 & \pmod{m_i} \\ x_i & \equiv 0 & \pmod{m_{i+1}} \\ & \vdots \\ x_i & \equiv 0 & \pmod{m_k} \end{align*} In other words, we set $a_i = 1$ and $a_j = 0$ for $j \neq i$.
What this system of congruences does is look for integers that divide evenly into every modulus except for $m_i$. If we can do this for each modulus, we can get a collection of terms independently to combine together to get our desired result.
One candidate that zeroes out all moduli except for $m_i$ is $n_i$, since it's the product of all the other moduli but relatively prime with $m_i$. However, $n_i$ is not necessarily congruent to 1 in modulo $m_i$. But since $\gcd(m_i, n_i) = 1$, there must exist an integer $b$, the multiplicative inverse of $n_i$, such that $b \cdot n_i \equiv 1 \pmod{m_i}$ and therefore, $x_i = b \cdot n_i$ is our solution.
That is, $x_i \equiv b \cdot n_i \equiv 1 \pmod{m_i}$ and since $m_j \mid n_i$ for $i \neq j$, we have $m_j \mid b \cdot n_i = x_i$. In other words, $x_i \equiv 0 \pmod{m_j}$.
To solve the original simultaneous congruences, we take each of the $x_i$'s and let $x = a_1 \cdot x_1 + \cdots + a_k \cdot x_k$. Then $x$ is a solution to the simultaneous congruence. To verify this we observe that for each $m_i$, we have \begin{align*} x &\equiv a_1 \cdot x_1 + \cdots + a_k \cdot x_k & \pmod{m_i} \\ &\equiv a_1 \cdot 0 + \cdots + a_{i-1} \cdot 0 + a_i \cdot 1 + a_{i+1} \cdot 0 + \cdots + a+k \cdot 0 & \pmod{m_i} \\ &\equiv a_i & \pmod{m_i} \end{align*}
We say that $x$ is the solution modulo $n = m_1 \cdots m_k$, since all integers that are congruent to $x$ will also satisfy the simultaneous congruences.
To see that our solution is unique, suppose we have two solutions $x_1$ and $x_2$. Then $x_1 - x_2 \equiv 0 \pmod{m_i}$ for every $i$. We must have $m_i \mid (x_1 - x_2)$ for each $i$. Here, we will rely on a theorem that you have proven:
If $a$ and $b$ are relatively prime, and $a \mid n$ and $b \mid n$, then $ab \mid n$.
Since all of our $m_i$ are pairwise relatively prime, $n = m_1 \cdots m_k$ also divides $x_1 - x_2$. Therefore, we have $x_1 \equiv x_2 \pmod n$.
Here is the problem of Sunzi stated again. \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*}
To solve this, we follow the proof of the Chinese Remainder Theorem. We start by labeling our moduli—the easiest way to do this is to take them in order (but you can choose whatever order you like), so we have $m_1 = 3, m_2 = 5, m_3 = 7$. Then we define $n = m_1 \cdot m_2 \cdot m_3 = 3 \cdot 5 \cdot 7$ to be the product of the moduli. We then compute each $n_i = \frac{n}{m_i}$. We have $$n_1 = 5 \cdot 7 = 35, \quad n_2 = 3 \cdot 7 = 21, \quad n_3 = 3 \cdot 5 = 15.$$ Next, we compute the inverses of the $n_i$'s. We have $$35^{-1} \equiv 2^{-1} \equiv 2 \pmod 3, \quad 21^{-1} \equiv 1^{-1} \equiv 1 \pmod 5, \quad 15^{-1} \equiv 1^{-1} \equiv 1 \pmod 7.$$ This gives us $$x_1 = 35 \cdot 2 = 70, \quad x_2 = 21 \cdot 1 = 21, \quad x_3 = 15 \cdot 1 = 15.$$
Finally, we compute $x = a_1 x_1 + a_2 x_2 + a_3 x_3 \pmod{105}$: \begin{align*} x &\equiv 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 &\pmod{105} \\ &\equiv 140 + 63 + 30 &\pmod{105} \\ &\equiv 233 & \pmod{105}\\ &\equiv 23 & \pmod{105} \end{align*}
One immediate application of this theorem is that we can represent integers as a collection of remainders. This allows us to split up large integers and perform arithmetic on them in many small pieces independent of each other. This is discussed in Section 4.4.4 of the textbook.
Cryptography is the study of how to transform information and communication so that it's concealed and secure. The most basic form of cryptography dates back to the classical era, via the use of substitution ciphers. These involve shifts of letters: if your cipher was shifted by 13, then you would map $a \rightarrow n, b \rightarrow o, c \rightarrow p, \dots$ and so forth. Such ciphers are still in use today, but not for secure communications. If you wanted to talk about your favourite currently screening movies and tv shows on social media or something, internet etiquette is to conceal such spoilers by running it through a ROT13 encoding, which is just a substitution cipher with shift 13 that was just described.
The key to making cryptography work is by ensuring the encoding of the information remains secret. This doesn't work very well for substitution ciphers because the encoding is very simple. In fact, if you read enough ROT13 spoilers, you can begin to see patterns of how words form. So one aspect of cryptography is ensuring that the key is complex and remains secret. However, this is only half the battle. The other problem that remains is how to communicate about the key.
In Canada, the banks collectively run a system called Interac, which, among other things, makes it very handy to transfer money via email and is why services like Venmo didn't really catch on. Suppose Alice and Bob, the two famous recurring characters of cryptography, want to transfer some Canadian money. So Alice logs onto her bank's website and initiates an email transfer that can be deposited by Bob into any bank account he wants once he gets the email. How does this stay secure? Alice will set a password that she communicates to Bob, who will then use the password to verify that he is allowed to accept the email transfer.
Hypothetically, what Alice needs to do is communicate the password to Bob in a secure way. What usually ends up happening is that Alice just emails Bob the password to the same account. This is bad, because if an eavesdropper, like Eve, gets access to Bob's email, then Bob is, as they say in Canada, hosed, because both the password and the email containing the transfer are sitting in Bob's email account. All Eve needs to do is use the password and then she can deposit the Canadian dollars into any bank account she wishes.
This highlights a common weakness: even though we may devise an unbreakable cryptographic scheme, if the key for that system is acquired, then we're screwed. This shifts the problem of secure communication from the message that we originally wanted to send to the problem of how to securely distribute our key.
One way to do this is to make it not a cryptographic problem anymore and do something like send the keys physically. This is what actually happened prior to communication with electronic computers, but situations that demand security, like communications with government agencies or banks may still use mail to send such keys.
The use of a secret key for encryption and decryption is called private-key cryptography. This is also called symmetric-key cryptography. This name hints at the root of our problem and a possible solution: what if we separate the encryption and decryption key?
This leads us to the idea of public-key cryptography, or asymmetric-key cryptography. Here, only the decryption keys are secret, while encryption keys are made public. This way, if Alice wants to send Bob a message that only Bob can read (perhaps containing Alice's credit card number or something), then Alice encrypts her message with Bob's public key, sends the encrypted message, and Bob would then decrypt the message.
The key to making this work is that the public and private keys need to be related in such a way that decryption is easy when the private key is known, but difficult when only the public key is known.
The most famous public-key cryptosystem (and definitely the most popular to teach in elementary number theory classes) is RSA, named for Rivest, Shamir, and Adleman who designed it in 1977 at MIT. RSA is commercially implemented in many Internet communication protocols currently in use and won Rivest, Shamir, and Adleman the Turing Award in 2002.
There are three parts to the system.
To see that this claim is true, we first recall that we have $$R \equiv C^d \equiv (M^e)^d \equiv M^{ed} \pmod n.$$ Since $ed \equiv 1 \pmod{(p-1)(q-1)}$, by the definitions of congruence and divisibility, we have $$ed = 1+k(p-1)(q-1)$$ for some integer $k$. This gives us $$R \equiv M^{1+k(p-1)(q-1)} \pmod n.$$
Now, we show that $R \equiv M \pmod p$. There are two cases: either $p \mid M$ or $p \nmid M$. In the first case, we have $M \equiv 0 \pmod p$, which gives $$R \equiv 0^{1+k(p-1)(q-1)} \equiv 0 \pmod p$$ and therefore $R \equiv 0 \equiv M \pmod p$. In the second case, $p \nmid M$ implies $\gcd(p,M) = 1$ and therefore, by Fermat's Little Theorem, $M^{p-1} \equiv 1 \pmod p$. Then we get $$R \equiv M(M^{p-1})^{k(q-1)} \equiv M\cdot 1^{k(q-1)} \equiv M \pmod p.$$ Therefore, $R \equiv M \pmod p$. A similar argument holds for $q$ and we can show $R \equiv M \pmod q$. Since $p$ and $q$ are distinct primes, we must have $\gcd(p,q) = 1$ and therefore, by the Chinese Remainder Theorem, we can put together the two congruences to get $R \equiv M \pmod{n}$.
So why is this secure? The publicly available information is $(e,n)$, which means that all an attacker needs is $d$. So how hard is finding $d$ based on $e$ and $n$? Since $d$ is the inverse of $e$ modulo $(p-1)(q-1)$, this means that one needs to find $p$ and $q$ from $n$. This means that if we can factor numbers into prime factors efficiently, then it is possible to recover $d$ efficiently.
What if we tried a more direct approach, like recovering $M$ from $M^e \bmod n$? In essence, we are talking about finding the $e$th modular root of a number. This is difficult to do if $n$ is not prime and would still depend on knowing $p$ and $q$. (There are deeper number theoretic reasons for this, having to do with Euler's $\varphi$ function)