Here is the proof of the theorem we mentioned from last class: that $a$ has an inverse in mod $m$ if $\gcd(a,m) = 1$.
By Bézout's lemma, there exist integers $n$ and $b$ such that $n \cdot m + b \cdot a = 1$. Then, \begin{align*} 1 &= n \cdot m + b \cdot a \\ &\equiv n \cdot m + b \cdot a & \pmod m\\ &\equiv n \cdot 0 + b \cdot a & \pmod m\\ &\equiv b \cdot a & \pmod m \end{align*}
Notice that we implicitly use reflexivity: since $1 = ab+mn$, we must have $1 \equiv_m ab + mn$.
One might ask whether there is any integer $m$ for which $\mathbb Z_m$ has a multiplicative inverse for all non-zero elements. Our discussion about prime numbers gives us a hint. But first, we need the following useful fact.
If $a$ and $m$ are relatively prime and $a \gt 1$, then the multiplicative inverse of $a$ modulo $m$ is unique.
This is not hard to show using the usual trick of considering two inverses, say $b$ and $c$, for $a$ and arriving at the fact that $b \equiv c$.
If $p$ is prime and $a \neq 0 \pmod p$, then $a$ has a multiplicative inverse mod $p$.
This is easy to see since every integer $2, \dots, m-1$ aren't divisors of $p$ and therefore share no common divisors with $p$.
When it exists, we denote the multiplicative inverse of $a$ by $a^{-1}$.
Up until now, we've been working in $\mathbb Z$, where "division" "doesn't work". However, we've proved sufficient conditions to create structures where "division" does work in a sense, in that multiplicative inverses are guaranteed to exist for every element. This means that we can solve linear equations like $$6x \equiv 144 \pmod{17}$$ using our usual algebraic techniques. In fact, assuming we were working with the same modulus, it's not hard to solve a system of equations in the usual way.
Technically speaking, these aren't equations because the items aren't being equated; we call these congruences instead.
So let's solve this congruence. Just like with ordinary equations, there are a few approaches we can take. One thing we might try is to compute $144 \pmod{17}$. Some quick math tells us that $144 \equiv 8 \pmod{17}$. This means we have $6x \equiv 8 \pmod{17}$. Now, we want to isolate the $x$, so we need to "divide" by 6. This amounts to finding an element $y$ such that $6y \equiv 1 \pmod{17}$. Doing some quick math, we get $6 \times 3 \equiv 18 \equiv 1 \pmod{17}$. This gives us $x \equiv 8 \times 3 \equiv 24 \equiv 7 \pmod{17}$.
Alternatively, we could have gotten rid of the 6 first and then solved the remaining congruence. This means we begin by multiplying both sides by 3 to get \[x \equiv 144 \times 3 \equiv 432 \equiv 7 \pmod{17}.\]
Now, you might look at this and go: wait a second, why couldn't we have just looked for an appropriate $x$ that satisfied $6x \equiv 8 \pmod{17}$? And that is a valid approach—in fact, for non-linear congruences, that is often the best you can hope to do. But the ability to deploy algebra in the way that we're used to may help us solve more complicated problems.
Before, we said that a structure where we have addition and multiplication is called a ring. But what happens when we have a ring that supports "division"? These structures are called fields. So the integers, $\mathbb Z$ can be said to form a ring with addition and multiplication, while $\mathbb Z_p$, the integers modulo a prime $p$, are a field. Another example of a field is the rational numbers, $\mathbb Q$.
One observation from the previous problem is that once we have the notion of equivalence, we can very quickly simplify some numbers by swapping them out with an equivalent but smaller number. How far can we take this idea?
One thing to consider is what else we might gain when every element in our structure has a unique multiplicative inverse. An interesting consequence is that such a structure can be said to be cyclic in some sense. We will now consider a result of Pierre de Fermat's that uses this notion for $\mathbb Z_p$, called Fermat's Little Theorem.
This is to distinguish it from the more famous Fermat theorem, Fermat's Last Theorem (there are no integers $a,b,c$ such that $a^n + b^n = c^n$ for $n \gt 2$). Much like Fermat's Last Theorem, Fermat stated the result in the mid 1600s but declined to give a proof of it because the proof was "too long".
While it would be about 400 years before Fermat's Last Theorem gets proven (by Andrew Wiles in 1995), Fermat's Little Theorem was proved only about 100 years later, by Leonhard Euler. The following proof, using modular arithmetic, is due to James Ivory in the early 1800s and a bit later by Dirichlet.
For all prime numbers $p$ and integers $a$ such that $\gcd(a,p) = 1$, $a^{p-1} \equiv 1 \pmod p$.
Before, we mentioned non-linear congruences. These are congruences $x^k \equiv a \pmod m$ with $k \geq 2$. For these congruences, there is often not much you can do except to try out numbers and look for a solution—which there may not be. Fermat's Little Theorem gives us a scenario in which we don't have to go searching and a way to simplify congruences with seeming large degree.
Consider $n \equiv (a \cdot 1) \cdot (a \cdot 2) \cdot \cdots \cdot (a \cdot (p-1)) \pmod p$. We can view this product in two ways.
First, we claim without proof that $$\{[a]_p, [2a]_p, \dots, [(p-1)a]_p\} = \{[1]_p,[2]_p,\dots,[p-1]_p\}.$$ This is really a claim about the cyclicity of the elements in $\mathbb Z_p$. That is, we can "cycle" through every element of $\mathbb Z_p$ by multiplying each element by some fixed integer $a$, as long as $a \not\equiv 0 \pmod p$.
If you want to prove this, there are two things to show:
Now, we will cite another useful result that we will not prove, but makes for an interesting exercise:
For all primes $p$, $(p-1)! \equiv -1 \pmod p$.
We can use this theorem together with our claim from above to conclude that $$n \equiv (a \cdot 1) \cdot (a \cdot 2) \cdot \cdots \cdot (a \cdot (p-1)) \equiv (p-1)! \equiv -1 \pmod p.$$
Next, we can rearrange the terms of the product to give us $n \equiv a^{p-1} \cdot (p-1)! \pmod p$. Again, by the cited theorem, we have $n \equiv a^{p-1} \cdot (-1) \pmod p$.
Putting these two equations together, we get that $n \equiv a^{p-1} \cdot (-1) \equiv -1 \pmod p$. Therefore, $a^{p-1} \equiv 1 \pmod p$.
A practical consequence of this theorem is that it allows us to very rapidly simplify congruences on large powers.
Let's compute $7^{315} \bmod 11$. Instead of performing division on $7^{315}$, we manipulate the exponent. Observing that $10 = 11-1$, we see that $315 = 10 \cdot 31 + 5$ by division. This gives us \begin{align*} 7^{315} &\equiv 7^{31 \cdot 10 + 5} &\pmod{11} \\ &\equiv (7^{10})^{31} \cdot 7^5 &\pmod{11} \\ &\equiv 1^{31} \cdot 49^2 \cdot 7 &\pmod{11} \\ &\equiv 5^2 \cdot 7 &\pmod{11} \\ &\equiv 25 \cdot 7 &\pmod{11} \\ &\equiv 3 \cdot 7 &\pmod{11} \\ &\equiv 21 &\pmod{11} \\ &\equiv 10 &\pmod{11} \\ \end{align*}
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.
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}.\]
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*} The English name of the theorem is largely due to L.E. Dickson in the 1920s, who discovered it through earlier translated work. Dickson was a faculty in the math department here—the Dickson Instructors in math are named after him.
Here is a quick example before we get into the proof. 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}$.