Number Theory: In Context and Interactive

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.

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?

xxxxxxxxxx

[mod(30*x,33)==18 for x in [5,16,27]]

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.