Definition 5.4.1.1.
A linear congruence is a congruence of the form
\begin{equation*}
a x \equiv b \pmod m,
\end{equation*}
where \(m\) is a positive integer, \(a\) and \(b\) are integers, and \(x\) is a variable.
Subsection 5.4.1 Linear congruences
We want to solve linear congruences. As motivation, note that if we wanted to solve \(ax = b\text{,}\) and \(a\) has a multiplicative inverse \(a^{-1}\text{,}\) then we would just multiply both sides by \(a^{-1}\) to solve, and get \(x = a^{-1} b\text{.}\) e.g., The solution to \(7x = 3\) is \(x = \frac{3}{7}\text{.}\) The same idea works for linear congruences if there exists an integer \(\abar\) such that \(a \abar \equiv 1 \pmod m\text{.}\) Such an integer is called an inverse of \(a\) modulo \(m\text{.}\)
Definition 5.4.1.2.
Let \(a\) and \(m\) be integers, with \(m \gt 1\text{.}\) A (multiplicative) inverse of \(a\) modulo \(m\) is an integer \(\abar\) such that \(a \abar \equiv 1 \pmod m\text{.}\)
Example 5.4.1.3. Modular inverses.
\(5\) is an inverse of \(7\) modulo \(17\text{,}\) since \(5 \cdot 7 \equiv 1 \pmod{17}\text{.}\) Note that an inverse is not unique. \(22\) is another inverse of \(7\) modulo \(17\text{,}\) since \(22 \cdot 7 \equiv 1 \pmod{17}\text{.}\) Inverses can be negative. For example, \(-12\) is an inverse of \(7\) modulo \(17\text{.}\) In fact, there are infinitely many inverses of \(7\) modulo \(17\text{.}\) Every integer in the congruence class of \(5\) modulo \(17\) is an inverse of \(7\) modulo \(17\)
\begin{equation*}
[5] = \set{5 + 17k \mid k \in \ZZ}.
\end{equation*}
In the example above, we see that the inverses of \(7\) modulo \(17\) form a congruence class. If an integer \(a\) has an inverse modulo \(m\text{,}\) this is what happens in general.
Theorem 5.4.1.4.
If \(\gcd(a,m) = 1\text{,}\) then the inverse of \(a\) modulo \(m\) exists. Furthermore, it is unique modulo \(m\text{.}\)
Proof.
Suppose \(\gcd(a,m) = 1\text{.}\) Then by Bézout, there exists integers \(s\) and \(t\) such that \(as + mt = 1\text{.}\) It follows that \(mt = 1 - as\text{,}\) so \(as \equiv 1 \pmod{m}\text{.}\) Thus \(s\) is an inverse of \(a\) modulo \(m\text{.}\)
Next, we show uniqueness. Suppose \(s\) and \(s'\) are inverses of \(a\) modulo \(m\text{.}\) We need to show \(s \equiv s' \pmod{m}\text{.}\) Since \(s\) and \(s'\) are inverses of \(a\) modulo \(m\text{,}\) there exists integers \(k \) and \(k'\) such that \(as = 1 + km\) and \(as' = 1 + k'm\text{.}\) Then
\begin{equation*}
a(s - s') = as - as' = (1 + km) - (1 + k'm) = m(k - k').
\end{equation*}
Then \(m\) divides \(a(s - s')\) and \(\gcd(a,m) = 1\text{,}\) so Lemma 5.3.3.21 implies \(m\) divides \(s - s'\text{.}\) It follows that \(s \equiv s' \pmod{m}\text{,}\) as desired.
Using modular arithmetic, we can see a few things that will simplify computations. Suppose \(\gcd(a,m) = 1\) so that \(a\) has an inverse modulo \(m\text{.}\) An inverse of \(a\) will be an inverse for every integer in the congruence class of \(a\) modulo \(m\text{.}\) We can use this to simplify our problem when \(\abs{a} \gt m\text{.}\) Furthermore, once an inverse is found, every integer in the congruence class of the inverse is also an inverse. This is helpful when we want to find an inverse with additional properties. For example, we may want to find an inverse that is positive and “small” since we are doing computations by hand.
Example 5.4.1.5. Modular inverse of \(253\) modulo \(8\).
Since \(253 \bmod{8} = 5\text{,}\) this reduces to finding an inverse of \(5\) modulo \(8\text{.}\) Since \(3 \cdot 5 \equiv 15 \equiv -1 \pmod{8}\text{,}\) we have that \(-3\) is an inverse of \(5\) modulo \(8\text{.}\) Every integer in the congruence class \([-3]\) is also an inverse. We want a positive inverse, so we can take \(-3 + 8 = 5\) as an inverse. In fact, since the inverse is unique modulo \(8\text{,}\) we just proved that this is the smallest positive integer that is an inverse of \(253\) modulo \(8\text{.}\)
We can use the modular inverse to solve linear congruences \(a x \equiv b\pmod m\) when \(\gcd(a, m) = 1\text{.}\) Namely, \(x \equiv \abar b \pmod m\text{.}\) When \(\gcd(a,m) \neq 1\text{,}\) the solution is a bit more subtle.
For small \(m\text{,}\) the inverse of \(a\) is easy to compute by inspection. For larger \(m\text{,}\) use Extended Euclidean algorithm. Specifically, if \(\gcd(a,m) = 1\text{,}\) there exists integers \(s\) and \(t\) such that
\begin{equation*}
1 = as + tm.
\end{equation*}
Then
\begin{equation*}
1 \equiv as \pmod m.
\end{equation*}
