Section6.5More complicated cases

Solving linear congruences is a completely solved problem (up to computer power). Usually one does not cover all cases in an introductory course, but in the following optional subsections we will introduce you to them, though not with all details.

Subsection6.5.1Moduli which are not coprime

Let's go back to the interact from before. What happens if I let the \(n_i\) NOT be relatively prime? Try some moduli which are not pairwise coprime.

The answer Qin discovered for getting CRT answers in this situation is that an answer exists as long as \(gcd(n_i,n_j)\) divides \(a_i-a_j\) for all \(i\) and \(j\). Lebèsgue was the first to rediscover this in the modern era, in 1859.

Subsection6.5.2Moduli which are prime powers

We already know the criterion for being able to solve a single linear congruence. Nonetheless, the CRT and its consequences force us to reconsider the case that comes up most naturally when trying to get coprime moduli. This is the prime power case. For instance, to solve a bunch of congruences \[x\equiv a_j\text{ mod }(n_j)\] we can start by solving congruences \[x\equiv a_j\text{ mod }(p^e)\] where \(p^e\) divides \(n_j\).

This is best approached via an extended example.

Example6.5.1Prime 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.

  • 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 this in the congruence yields \[2x\equiv 2(4+5k)\equiv 2\cdot 4+2\cdot 5k\equiv 3\text{ mod (25),}\] or, rearranging (but keeping everything unmultiplied), \[3-2\cdot 4\equiv 2\cdot 5k\text{ mod }(5^2)\, .\]
  • Now, we know that \(5\mid 3-2\cdot 4\), because we already know that \(3\equiv 2\cdot 4\) mod (5) solved our original congruence. So we can cancel out \(5\) from the entire congruence to get that \[\frac{3-2\cdot 4}{5}\equiv 2k\text{ mod (5)}\; .\]
  • 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 \[4+5k=4+5\cdot 2=14\text{ mod }(5^2)\] as the solution.
  • And indeed \(2\cdot 14=28\equiv 3\) mod (\(25\)).

Now, that was a lot. Let's do it all again, more tersely, to get a solution module \(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 \[2\cdot 5^2 k \equiv 3-2\cdot 14\text{ mod }(5^3)\; .\]
  • Since we know that \(14\) solves \(2x\equiv 3\) mod (\(5^2\)), that means (by definition of congruence) that \[5^2|3-2\cdot 14\; ,\] so we can divide "all three sides" of the last congruence by \(5^2\).
  • This yields \[2k\equiv \frac{3-2\cdot 14}{5^2}\equiv \frac{-25}{5^2}\equiv -1\text{ mod }(5)\; .\]
  • Solving this yields, of course, \(k\equiv 2\) mod (5), so \[x\equiv 14+5^2 \cdot 2\equiv 64\text{ mod }(125)\; ,\] 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.