Solving Linear Congruence Equations

Question

Solve the following congruence problem:

$$N\equiv0 (\text{mod }11)$$ $$N\equiv0 (\text{mod }5)$$ $$N\equiv4 (\text{mod }9)$$ $$N\equiv6 (\text{mod }8)$$ $$N\equiv0 (\text{mod }7)$$

I first noted that

$$\begin{align*} N\equiv0 (\text{mod }11\cdot5\cdot7) &\equiv0 (\text{mod }385)\\ \end{align*}$$

I now have $3$ equations:

$$N\equiv4 (\text{mod }9)$$

$$N\equiv6 (\text{mod }8)$$

$$N\equiv0 (\text{mod }385)$$

I then wrote

$$\begin{align} N=(9\cdot8\cdot{a})+(9\cdot385\cdot{b})+(8\cdot385\cdot{c}) &=(72\cdot{a})+(3465\cdot{b})+(3080\cdot{c}) \end{align}$$

So then

$$4\equiv 3080c \equiv 2c(\text{mod }9) \Rightarrow c=2$$

$$6\equiv 3465b \equiv b(\text{mod }8) \Rightarrow b=6$$

$$0\equiv 72a \equiv 72a(\text{mod }385) \Rightarrow a=0$$

Then

$$N=(72\cdot0) + (3465\cdot6) + (3080\cdot2)=26950$$

Plugging $N$ back into the equation works out but are there more solutions? Infinitely many? If there is a more efficient way to solve this, I would be interested as well.

Answer 1

I would first group together the congruences $N\equiv 0 \pmod{5,7,11}\iff N\equiv 0\pmod{5\cdot 7\cdot 11=385}$

Second, I'd solve the system $\;\begin{cases}N\equiv 4\pmod 9, \\ N\equiv 6\pmod 8.\end{cases}$

The effective version of the Chinese remainder theorem yields the solution to a system of congruences $\;\begin{cases}N\equiv \alpha\pmod a, \\ N\equiv \beta\pmod b,\end{cases}\;$ when the moduli are coprime and we have a Bézout's relation: $\;ua+vb=1$. This solution is $$N\equiv \beta ua+\alpha vb \pmod{ab}. $$

Now, as $9-8=1$, the solutions to the second group of congruences is $$N\equiv6\cdot9-4\cdot8=22\pmod{72}.$$

Last, we have to find a Bézout's relation between $385$ and $72$ to solve the system of congruences $\;\begin{cases}N\equiv 0\pmod{385},\\ N\equiv 22\pmod{72}.\end{cases}$

This is done with the extended Euclidean algorithm: $$\begin{array}{rrrr} r_i&u_i&v_i&q_i \\ \hline 385&1&0\\ 72&0&1&5 \\ \hline 25&1&-5&2 \\ 22&-2&11&1 \\ 3&3&-16&7 \\ \color{red}{1}&\color{red}{-23}& \color{red}{123} \\\hline \end{array}$$ Thus a Bézout's relation is $\; -23\cdot 385+123\cdot75=1$, and the solution of the system of congruences is $$N\equiv-22\cdot23\cdot 385+0\cdot123\cdot 72=-194810\equiv \color{red}{-770}\pmod{72\cdot 385= \color{red}{27720}}.$$

Answer 2

I would solve each equation, and modify the solution as I go.

After the fist two equations.

$N = 55k$

Plugging that into the 3rd.

$55k \equiv k\pmod 9\\ k = 4$

$N = 4\cdot 55 + 55\cdot 9\cdot k = 220+495 k$

And continue this way through the last 2 equations.

$220+495k \equiv 4 -k\pmod 8$

$k\equiv -2 \equiv 6\pmod 8$

$N = 3190 + 3960k \equiv 5 + 5k \pmod 7\\ k = 6\\ N = 26,950 + 27,720k$

Answer 3

By CRT there are infinitely many solutions with $$N=26950 \pmod{11\cdot 5\cdot 9 \cdot 8 \cdot 7}$$