Section6.2A bigger strategy

The previous strategy always works. However, it can be very tedious to find that first solution if the modulus is bigger.

Hence, we can adopt some other propositions in the effort to simplify our congruence to its bare bones.

  • The following two strategies seem very reasonable from our experience with integers.
    • If \(a\), \(b\), and \(n\) all are divisible by a common divisor, we can cancel that out (though see below for a caveat with this).
    • If \(a\) and \(b\) share a common divisor which is coprime to the modulus, we can cancel that.
    We'll postpone the precise statements and proofs.
  • The following two additional strategies seem counterintuitive, but make sense in the wacky world of modular arithmetic.
    • We could multiply \(a\) and \(b\) by something coprime to \(n\). If, after reducing modulo \(n\), that makes \(a\) or \(b\) smaller, then that was a good idea!
    • We can add some multiple of \(n\) to \(b\). Again, if that happens to make \(a\) and (the new) \(b\) share a factor, then that was a good idea!
These steps may be applied in any order, though typically the first two are done as often as possible. We'll prove these things are legal after we do a full example.

Example6.2.1A big example

Let's do a big problem exemplifying all the steps.\[\text{ Solve }30x\equiv 18\text{ mod }(33)\; .\]

  1. First, note that all three are divisible by \(3\). So right away we should simplify by dividing by 3 - keeping in mind that our final solution will need to be modulo 33, not modulo 11! We should end up with \(gcd(30,33)=3\) total solutions.
  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\), we can divide out by \(2\) without any other muss. \[5x\equiv 3\text{ mod }(11)\]
  3. Let's avoid trial and error as long as possible by trying something else. Anyway, \(x=1\) and \(x=2\) don't work right away, and I am lazy.
  4. 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\), but that gives \[5x\equiv 14\text{ mod }(11)\] and 14 doesn't share a divisor with \(5\) (from the \(5x\)).
    • If I try \(3+22=25\), giving \[5x\equiv 25\text{ mod }(11)\] then \(25\) does share a divisor with \(5\).
  5. Now I can go back and reduce \(5x\equiv 25\) mod (11) to \[x\equiv 5\text{ mod (}11)\] And that's the answer! Or is it?
  6. Remember that we started modulo 33, and that all the answers will be equivalent modulo 11. So I see that \[x=5+11t\text{ for }t\in\mathbb{Z}\] will be the answer, which is the equivalence classes \(\{[5],[16],[27]\}\).

Does it check out?

Let's use the other possible step; that was a trick to multiply \(a\) and \(b\) by something which would reduce; ideally it would reduce \([a]\equiv [1]\).

  • We were at \(5x\equiv 3\) mod (11).
  • Multiplying \(a=5\) and \(b=3\) by \(9\), which is coprime to \(11\), gives us \[45x\equiv 27\text{ mod }(11)\; .\]
  • This reduces to \(x\equiv 5\), and gives the same answer as before (provided we remember to get all answer modulo 33).

Subsection6.2.1Following Up

Try one of these on your own now. The exercises provide other interesting practice.

  • \(7x\equiv 8\) mod (15)
  • \(6x\equiv 8\) mod (15)
  • \(7x\equiv 8\) mod (14)
  • \(6x\equiv 8\) mod (14)

Here are formal statements and proofs of the propositions we used.

Left to reader: Why do the other two pieces of the strategy not need further proof? Where have we seen them before?