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. Alternatively, there may be more than one solution.
Consider $6x \equiv 2 \pmod 8$. Since $\gcd(6,8) \gt 1$, 6 doesn't have an inverse modulo 8. However, a quick search reveals that $x \equiv 3 \pmod 8$ is a solution to our congruence, since $6 \times 3 \equiv 18 \equiv 2 \pmod 8$. However, we shouldn't stop: this isn't the only solution. If we keep going, we find that $6 \times 7 \equiv 42 \equiv 2 \pmod 8$. So there are two possible solutions for $x$ (7 is the last one, since the next number we'd test is $8 \equiv 0 \pmod 8$ and we start over).
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 and that this solution is unique.
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*}
For all integers $a_1$ and $a_2$, and positive integers $m_1$ and $m_2$, if $\gcd(m_1, m_2) = 1$, then the simultaneous linear congruences \begin{align*} x &\equiv a_1 \pmod{m_1} \\ x &\equiv a_2 \pmod{m_2} \end{align*} have a unique solution modulo $m_1 m_2$. That is, if $x = n$ is one particular solution, then the solutions are given by the set of all integers such that \[x \equiv n \pmod{m_1 m_2}.\]
Let $a_1, a_2$ be arbitrary integers and let $m_1, m_2$ be arbitrary positive integers with $\gcd(m_1, m_2) = 1$.
First, we will consider a solution $x_1$ to the simpler simultaneous congruences \begin{align*} x_1 & \equiv 1 & \pmod{m_1} \\ x_1 & \equiv 0 & \pmod{m_2} \end{align*} First, we need to look for an integer that is equivalent to $0 \pmod{m_2}$ but not $0 \pmod{m_1}$. We claim that $m_2$ is such an integer. Since $\gcd(m_1, m_2) = 1$, we have \begin{align*} m_2 & \not\equiv 0 & \pmod{m_1} \\ m_2 & \equiv 0 & \pmod{m_2} \end{align*} Furthermore, since they are coprime, $m_2$ has an inverse modulo $m_1$. That is, there must exist an integer $b$ such that $m_2 \cdot b \equiv 1 \pmod{m_1}$. This gives us \begin{align*} m_2 \cdot b & \equiv 1 & \pmod{m_1} \\ m_2 \cdot b & \equiv 0 & \pmod{m_2} \end{align*} Now, notice that we can repeat the same argument but for the congruences \begin{align*} x_2 & \equiv 0 & \pmod{m_1} \\ x_2 & \equiv 1 & \pmod{m_2} \end{align*} and we can obtain that $x_2 = m_1 \cdot c$, where $m_1 \cdot c \equiv 1 \pmod{m_2}$.
Now, to solve the original simultaneous congruences, we take $x_1 = m_2 \cdot b$ and $x_2 = m_1 \cdot c$ and let \[x = a_1 \cdot x_1 + a_2 \cdot x_2 = a_1 m_2 b + a_2 m_1 c.\] Then $x$ is a solution to the simultaneous congruence. To verify this we observe that we have \begin{align*} x &\equiv a_1 \cdot x_1 + a_2 \cdot x_2 &\pmod{m_1} \\ &\equiv a_1 (m_2 \cdot b) + a_2 (m_1 \cdot c) &\pmod{m_1} \\ &\equiv a_1 \cdot 1 + a_2 \cdot 0 &\pmod{m_1} \\ &\equiv a_1 &\pmod{m_1} \\ \\ x &\equiv a_1 \cdot x_1 + a_2 \cdot x_2 &\pmod{m_2} \\ &\equiv a_1 (m_2 \cdot b) + a_2 (m_1 \cdot c) &\pmod{m_2} \\ &\equiv a_1 \cdot 0 + a_2 \cdot 1 &\pmod{m_2} \\ &\equiv a_2 &\pmod{m_2} \end{align*}
We say that $x$ is the solution modulo $m_1 m_2$, 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 both $i = 1,2$. We must have $m_i \mid x_1 - x_2$ for both $i = 1, 2$. Here, we will rely on the following theorem:
If $a$ and $b$ are relatively prime, and $a \mid n$ and $b \mid n$, then $ab \mid n$.
Since $m_1$ and $m_2$ are relatively prime, $m_1 m_2$ also divides $x_1 - x_2$. Therefore, we have $x_1 \equiv x_2 \pmod{m_1 m_2}$.
Consider the simulatneous congruences \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \end{align*}
Since $\gcd(3,5) = 1$, the Chinese Remainder Theorem tells us the solutions are unique modulo 15. Since the numbers are small enough, we can simply run through them: 3, 8, and 13 are integers between 0 and 14 that are congruent to $3 \pmod 5$.
Now, for each of these, we note that $3 \equiv 0 \pmod 3$, $8 \equiv 2 \pmod 3$, and $13 \equiv 1 \pmod 3$, so we can conclude that our desired solution is $8 \pmod{15}$.
Taking this result, we can apply it to the original problem of Sunzi: \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \\ x &\equiv 2 &\pmod 7 \end{align*} Since we showed that $x \equiv 8 \pmod{15}$ satisfies the first two congruences, solving these three simultaneous congruences amounts to solving the congruences \begin{align*} x &\equiv 8 &\pmod{15} \\ x &\equiv 2 &\pmod 7 \end{align*} Since $\gcd(7,15) = 1$, we can simply apply the CRT again.
One can generalize this result to multiple moduli.
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$.
We won't prove this. Finally, we return to the motivating problem we started out with.
For all integers $a$ and positive integers $m_1, m_2$, if $\gcd(m_1, m_2 = 1$, then the simultaneous congruences \begin{align*} x & \equiv a & \pmod{m_1} \\ x & \equiv a & \pmod{m_2} \end{align*} have the same solutions as $x \equiv a \pmod{m_1 m_2}$.
Let $a, m_1, m_2$ be arbitrary with $\gcd(m_1, m_2) = 1$. By the Chinese Remainder Theorem, there exists a solution to the simultaneous congruences, say $x \equiv n \pmod{m_1m_2}$.
We observe that $n = a$ is a possible solution, since $a \equiv a \pmod{m_1}$ and $a \equiv a \pmod{m_2}$. So we have that $n \equiv a \pmod{m_1 m_2}$.
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$. We apply the same process for $q$ to show that $R \equiv M \pmod q$. Since $p$ and $q$ are distinct primes, we must have $\gcd(p,q) = 1$ and so, by the Chinese Remainder Theorem, we can put together the two congruences to get $R \equiv M \pmod{n}$. This confirms that the encryption and decryption operations "work": we get the same message $M$ out as we put in.
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. Unfortunately (or fortunately?) we don't know how to find prime factors of a number efficiently using classical computers (if we had a quantum computer, it is possible—something the NSA is quite worried about).
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, which is discussed in Section 9.10 of the textbook)