Subsection6.5.1Factoring the modulus
The reason the fundamental theorem is so useful for congruences is that prime powers (for different primes) are automatically relatively prime to each other. So in using the Chinese Remainder Theorem (Theorem 5.3.1) we don't have a spend time looking for coprime factors; we can just factor into prime powers using the Fundamental Theorem of Arithmetic. So here is a useful repositioning of Proposition 5.4.2.
Proposition6.5.1Converting to and from prime powers
Suppose that \(X\equiv Y\) (mod \(N\)), and \(N=\prod p_i^{e_i}\). Then we have two directions of equivalence between a congruence and a system of congruences.
Certainly if \(N\) divides \(X-Y\), so does a factor of \(N\), so \(X\equiv Y\) (mod \(p_i^{e_i}\)) for each of prime power factors of \(N\). (Once again, solutions to the “big” congruence are also solutions to a system of many little ones.
But by their nature, the prime powers in a factorization are all coprime to each other, so if we are given a solution pair \((X_i,Y_i)\) to each of the congruences \begin{equation*}X_i\equiv Y_i\text{ (mod }p_i^{e_i}) \end{equation*} then when combined they will give a solution of \begin{equation*}X\equiv Y\text{ (mod }N\text{)}\end{equation*}
That means that any question about congruences is really a question about congruences modulo prime powers. We will use this fact again and again in the remainder of the text, and it is a huge reason why the CRT is so intensely powerful.
Similarly, referring to Subsection 5.5.2, what if one has one complicated congruence with coefficients and a composite modulus \(N\)? \begin{equation*}Ax\equiv B\text{ (mod }N)\end{equation*} Just take \(N=p_1^{e_1}\cdots p_k^{e_k}\) and then solve all the congruences \(Ax\equiv B\) (mod \(p_i^{e_i}\)) first. Then use the CRT to ‘patch’ them together for a final solution. This is a little tedious, but certainly doable.
Example6.5.2
Let's solve \begin{equation*}21x\equiv 31 \text{ mod }180\end{equation*} this way.
Subsection6.5.2Moduli which are prime powers¶ permalink
When it comes to linear congruences, these consequences of the Chinese Remainder Theorem and FTA allow us to reconsider the prime power case with a more subtle tool. Assume that in solving a bunch of congruences \begin{equation*}x\equiv a_j\text{ (mod }n_j)\end{equation*} we would like to start by solving congruences \begin{equation*}x\equiv a_j\text{ (mod }p^e)\end{equation*} where \(p^e\) divides \(n_j\).
The general approach is then to first solve modulo \(p\), in the hope that it could lead to a solution modulo \(p^e\). Consider this extended example.
Example6.5.3Prime Power Congruences
Let \(f(x)=2x-3\). The only solution of \(2x\equiv 3\) (mod \(5\)) is clear; it is \(x=[4]\). How might we get solutions (mod \(25\)) from this? Here are some steps.
First, any solution of \(2x\equiv 3\) (mod \(5^2\)) is also a solution of \(2x\equiv 3\) (mod \(5\)). So \(x\equiv 4+5k\) (mod \(25\)) for some \(k\), since \([4]=\{4+5k|k\in\mathbb{Z}\}\).
Plugging \(4+5k\) in the congruence yields \begin{equation*}2x\equiv 2(4+5k)\equiv 2\cdot 4+2\cdot 5k\equiv 3\text{ (mod }25\text{),}\end{equation*} or, rearranging (but keeping everything unmultiplied), \begin{equation*}3-2\cdot 4\equiv 2\cdot 5k\text{ (mod }5^2)\, .\end{equation*}
Now, we know that \(5\mid 3-2\cdot 4\), because we already know that \(4\) solved our original congruence: \begin{equation*}3\equiv 2\cdot 4\end{equation*} So we can cancel out \(5\) from the entire congruence to get that \begin{equation*}\frac{3-2\cdot 4}{5}\equiv 2k\text{ (mod }5\text{)}\; .\end{equation*} This simplifies to \(-1\equiv 2k\) (mod \(5\)), which has solution \(k\equiv 2\) (mod \(5\)).
Hence, using this \(k\) and plugging it back in to get a solution to \(2x\equiv 3\) (mod \(5^2\)), we get \begin{equation*}4+5k=4+5\cdot 2=14\text{ (mod }5^2)\end{equation*} as the solution. And indeed \(2\cdot 14=28\equiv 3\) (mod \(25\)).
Example6.5.4
Let's do it all again, more tersely, to get a solution to \(2x\equiv 3\) modulo \(5^3=125\).
I already know that \([14]\) is the solution to \(2x\equiv 3\) (mod \(5^2\)).
That means that a solution to \(2x\equiv 3\) (mod \(5^3\)) must look like \(14+5^2 k\).
Plugging this in gives me \(2(14+5^2 k)\equiv 3\) (mod \(5^3\)), which rearranges to \begin{equation*}2\cdot 5^2 k \equiv 3-2\cdot 14\text{ (mod }5^3)\; .\end{equation*}
Since we know that \(14\) solves \(2x\equiv 3\) (mod \(5^2\)), that means (by definition of congruence) that \begin{equation*}5^2\mid 3-2\cdot 14\; ,\end{equation*} so we can divide “all three sides” of the last congruence by \(5^2\).
This yields \begin{equation*}2k\equiv \frac{3-2\cdot 14}{5^2}\equiv \frac{-25}{5^2}\equiv -1\text{ (mod }5)\; .\end{equation*}
Solving this yields, of course, \(k\equiv 2\) (mod \(5\)), so \begin{equation*}x\equiv 14+5^2 \cdot 2\equiv 64\text{ (mod }125)\; ,\end{equation*} and indeed \(2\cdot 64=128\equiv 3\) (mod \(125\)) works.
You can do this as often as you like, and (properly interpreted) it will yield all solutions of your congruence modulo \(p^e\), one step at a time. We'll see a generalization of this in Section 7.2.
