Example5.2.2A big example

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

1. First, note that all three of the coefficients and modulus are divisible by \(3\). 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\), 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\), 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\), giving \begin{equation*}5x\equiv 25\text{ (mod }11)\end{equation*} then \(25\) does share a divisor with \(5\).

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+11t\text{ for }t\in\mathbb{Z}\end{equation*} will be the answer, which is the three equivalence classes \(\{[5],[16],[27]\}\).

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…

Example5.2.3

Let's finish the previous example gain, but using the other possible counterintuitive step. That was the 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 \begin{equation*}45x\equiv 27\text{ (mod }11)\; .\end{equation*}

• This reduces to \(x\equiv 5\), and gives the same answer as before (provided we remember to get all possible answers modulo 33).