Skip to main content
Logo image

Section 5.2 A Strategy For the First Solution

The previous proposition always works. However, it can be very tedious to find that first solution if the modulus is not small. This section is devoted to strategies 1  for simplifying a congruence so that finding such a solution is easier.

Example 5.2.2. A big example.

Let’s do a big problem exemplifying all the strategies; we will break it up into possible steps you might do.
\begin{equation*} \text{ Solve }30x\equiv 18\text{ (mod }33)\text{.} \end{equation*}
  1. First, note that all three of the coefficients and modulus are divisible by \(3\text{.}\) So right away we should simplify by dividing by 3. But keep in mind that our final solution will need to be modulo 33, not modulo eleven! We should still end up with \(\gcd(30,33)=3\) total solutions, and if we don’t, we have messed up somewhere.
  2. Now we have \(10x\equiv 6\) (mod \(11\)). (Again, although this will have one solution modulo 11, we will need to get the other two solutions modulo 33.) Since 10 and 6 are both divisible by 2, and since \(\gcd(2,11)=1\text{,}\) we can divide the coefficients (not modulus) by \(2\) without any other muss.
    \begin{equation*} 5x\equiv 3\text{ (mod }11\text{)} \end{equation*}
  3. So take \(5x\equiv 3\) (mod \(11\)), and let’s try to replace \(3\) by another number congruent to 3 modulo 11 which would allow me to use the above steps again.
    • I could try \(3+11=14\text{,}\) but that gives
      \begin{equation*} 5x\equiv 14\text{ (mod }11) \end{equation*}
      and 14 doesn’t share a divisor with \(5\) (from the \(5x\)).
    • If I try \(3+22=25\text{,}\) giving
      \begin{equation*} 5x\equiv 25\text{ (mod }11) \end{equation*}
      then \(25\) does share a divisor with \(5\text{.}\)
  4. Now I can go back and reduce \(5x\equiv 25\) (mod \(11\)) to
    \begin{equation*} x\equiv 5\text{ (mod }11\text{)} \end{equation*}
    And that’s the answer!
  5. Or is it? Remember in the first step that we started modulo 33, and that all the answers will be equivalent modulo 11. So we see that
    \begin{equation*} x=5+11k\text{ for }k\in\mathbb{Z} \end{equation*}
    will be the answer, which is the three equivalence classes \(\{[5],[16],[27]\}\text{.}\)
Does it check out?
One final observation is that we avoided trial and error as long as possible. At various points we could have done so, but \(x=1\) and \(x=2\) wouldn’t have worked right away, and I am lazy…

Example 5.2.3.

Let’s finish the previous example again, but using the other possible counterintuitive strategy. That was the trick to multiply \(a\) and \(b\) by something which would reduce; ideally it would reduce \([a]\equiv [1]\text{.}\)
  • We were at \(5x\equiv 3\) (mod \(11\)).
  • Multiplying \(a=5\) and \(b=3\) by \(9\text{,}\) which is coprime to \(11\text{,}\) gives us
    \begin{equation*} 45x\equiv 27\text{ (mod }11)\text{.} \end{equation*}
  • This reduces to \(x\equiv 5\text{,}\) and gives the same answer as before (provided we remember to get all possible answers modulo 33).

Example 5.2.4.

Try completely solving one of the following two congruences (Exercise 5.6.3) on your own now, before moving on. The rest of the Exercises provide other interesting practice.
  • \(7x\equiv 8\) (mod \(15\))
  • \(6x\equiv 8\) (mod \(14\))

Example 5.2.5.

Finally, let’s see examples of using the strategies poorly.
First, suppose \(6x\equiv 12\) (mod \(4\)). Then we could divide all terms by \(2\text{,}\) yielding \(3x\equiv 6\) (mod \(2\)), and then reducing everything modulo two we obtain \(x\equiv 0\text{,}\) or that the solution is all even \(x\text{.}\) If we had instead canceled the \(2\) from only the \(6x\equiv 12\) portion, we would have gotten \(3x\equiv 6\) (mod \(4\)), which is \(-x\equiv 2\) or \(x\equiv 2\) modulo four, which is only half of the true solutions.
As a similar example, suppose we want to solve \(7x\equiv 7\) (mod \(12\)). If we used cancellation the solution would obviously be \(x\equiv 1\text{.}\) Set this aside and instead multiply \(7x\) and \(7\) by \(2\) in order to obtain \(14x\equiv 14\) which simplifies to \(2x\equiv 2\) (mod \(12\)), which now looks like an easy target for cancelling \(2\) from all three numbers to obtain \(x\equiv 1\) (mod \(6\)), which is twice the true solutions.
The moral of the story is that while some structure is preserved when we don’t stick to numbers coprime to the modulus, it’s very easy to remove or add spurious solutions, so it must be avoided.
Here are formal statements and proofs of the propositions we used.
Like many such proofs, you basically follow your nose.
First write \(ad\equiv bd\) (mod \(nd\)) as \(nd \mid ad-bd\text{,}\) or \(ad-bd=k(nd)\) for some \(k\in\mathbb{Z}\text{.}\) We rewrite this as \(d(a-b)=d(kn)\text{.}\)
Since \(d\neq 0\text{,}\) asserting \(d(a-b)=d(kn)\) is equivalent to saying \(a-b=kn\text{,}\) which is of course by definition saying that \(a\equiv b\) (mod \(n\)).
Since all steps were equivalences, both statements are equivalent.
We already essentially know the direction when we assume \(a\equiv b\) from Proposition 4.3.2. I’ll sketch the proof of the cancellation direction; see Exercise 5.6.2 and Exercise 5.6.7.
  • Use the definitions as above, starting with the \(ad\) situation.
  • You should have that \(n\) divides some stuff, which is itself a product of \(d\) and other stuff.
  • We had a proposition somewhere about coprimeness and division; what remains should yield us \(a\equiv b\) (mod \(n\))
The reader should note that we roughly follow [E.2.1, pp. 50-51] in this, but that an alternate (or supplemental?) approach using the Bezout identity is followed in texts like [E.2.4] or [E.2.13].