##
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.

###
Fact 5.2.1. Strategies that work for simplifying congruences.

We can do two main types of simplification. First, there are two types of cancellation.

If \(a\text{,}\) \(b\text{,}\) and \(n\) all are divisible by a common divisor, we can cancel that divisor out (keeping in mind that we still will need our final solution to be modulo \(n\)).

If \(a\) and \(b\) share a common divisor which is coprime to the modulus, we can cancel that divisor from \(a,b\) (only).

See Propositions

5.2.6 and

5.2.7 for precise statements and proofs.

Secondly, there are two counterintuitive operations that may lead to a simpler congruence (using least nonnegative residues).

We could *multiply* \(a\) and \(b\) by something coprime to \(n\text{.}\) If, after reducing modulo \(n\text{,}\) that makes \(a\) or \(b\) smaller, then that was a good idea!

We can *add* some multiple of \(n\) to \(b\text{.}\) Again, if that happens to make \(a\) and (the new) \(b\) share a factor, then it was a good idea!

These four steps may be applied in any order, though typically the first two are done as often as possible. See

Example 5.2.5 for why

*coprime* is necessary in two of the steps.

###
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*}

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.

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*}

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{.}\)

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!

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.

###
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.

###
Proposition 5.2.6. Canceling, Part I.

If \(d\neq 0\text{,}\) then \(ad\equiv bd\) (mod \(nd\)) precisely for the same \(a, b, n\) as when \(a\equiv b\) (mod \(n\)).

### Proof.

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.

###
Proposition 5.2.7. Canceling, Part II.

If \(d\neq 0\) and \(\gcd(d,n)=1\text{,}\) then \(ad\equiv bd\) (mod \(n\)) precisely for the same \(a, b, n\) as when \(a\equiv b\) (mod \(n\)).

### Proof.

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\))