Let's prove this theorem from last class.
If integers $m \gt 0$ and $a$ are relatively prime, then $a$ has a multiplicative inverse mod $m$. That is, there exists an integer $b$ such that $a \cdot b = 1 \pmod m$.
By Bézout's lemma, there exist integers $n$ and $b$ such that $n \cdot m + b \cdot a = 1$. Then, \begin{align*} [1]_m &= [n \cdot m + b \cdot a]_m \\ &= [n]_m \cdot [m]_m + [b]_m \cdot [a]_m \\ &= [n]_m \cdot [0]_m + [b]_m \cdot [a]_m \\ &= [b]_m \cdot [a]_m \end{align*}
The notation in the above proof takes the approach of being explicit about working with equivalence classes. Another way of writing the equational reasoning in the above proof is \[1 \equiv n \cdot m + b \cdot a \equiv n \cdot 0 + b \cdot a = b \cdot a \pmod m.\]
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}$.
Before, we said that a structure where we have addition and multiplication is called a ring. But what happens when we have a structure 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$.
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 we must verify:
Now, we will cite another useful result that you have pretty much proved, though stated in a different form:
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*}