Let's proceed with the proof of the Chinese Remainder Theorem.
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}$.
Recall the simultaneous congruences \begin{align*} x &\equiv 2 &\pmod 3 \\ x &\equiv 3 &\pmod 5 \end{align*}
We had already shown that the 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).
This problem of finding prime factors is the problem of finding divisors that we discussed earlier. Older RSA keys range from hundreds of bits to 1024 while modern key sizes are typically 2048 or 4096 bits. If the key size is 4096 bits, then the difference between an $O(n)$ algorithm like our naive divisor search and a $O(\log n)$ algorithm is proportional to the difference between $2^{4096}$ and $4096$. Note that \begin{align*} 2^{4096} = &\ 10443888814131525066917527107166243825799642490473 \\ & \ 83780384233483283953907971557456848826811934997558 \\ & \ 34089010671443926283798757343818579360726323608785 \\ & \ 13652779459569765437099983403615901343837183144280 \\ & \ 70011855946226376318839397712745672334684344586617 \\ & \ 49680790870580370407128404874011860911446797778359 \\ & \ 80290066869389768817877859469056301902609405995794 \\ & \ 53432823469303026696443059025015972399867714215541 \\ & \ 69383555988529148631823791443449673408781187263949 \\ & \ 64751001890413490084170616750936683338505510329720 \\ & \ 88269550769983616369411933015213796825837188091833 \\ & \ 65675122131849284636812555022599830041234478486259 \\ & \ 56744921946170238065059132456108257318353800876086 \\ & \ 22102834270197698202313169017678006675195485079921 \\ & \ 63641937028537512478401490715913545998279051339961 \\ & \ 15517942711068311340905842728842797915548497829543 \\ & \ 23534517065223269061394905987693002122963395687782 \\ & \ 87894844061600741294567491982305057164237715481632 \\ & \ 13806310459029161369267083428564407304478999719017 \\ & \ 81465763473223850267253059899795996090799469201774 \\ & \ 62481771844986745565925017832907047311943316555080 \\ & \ 75682218465717463732968849128195203174570024409266 \\ & \ 16910874148385078411929804522981857338977648103126 \\ & \ 08590300130241346718972667321649151113160292078173 \\ & \ 8033436090243804708340403154190336 \end{align*}
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 also 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)