Solution of a system of congruence equations

45 Views Asked by At

Consider the following system out of which I want to find all possible values of $\lambda$. \begin{eqnarray} 1287\lambda\equiv0 (\mathrm{mod}\ 6)\label{eq1}\\ 165\lambda\equiv0 (\mathrm{mod}\ 4)\label{eq2}\\ 9\lambda\equiv0 (\mathrm{mod}\ 2)\label{eq3} \end{eqnarray} Since I am not comfortable with the Chinese Remainder Theorem, I have tried to proceed with direct substitution. \begin{eqnarray} 1287\lambda=6k\Rightarrow\lambda=\frac{2k}{429}\label{eq4}\\ 165\frac{2k}{429}=4r\Rightarrow k=\frac{858r}{165}\label{eq5}\\ \lambda=\frac{4r}{165}\label{eq6}\\ 9\lambda=2t\Rightarrow r=\frac{55t}{6}\label{eq7}\\ \lambda=\frac{2t}{9}\\ \end{eqnarray} i.e. we seek $t$ such that $2t\equiv0 (\mathrm{mod}\ 9)\Rightarrow t\equiv0 (\mathrm{mod}\ 9)$ i.e. $t=9,18,\dots$. Thus, the possible values of $\lambda$ are $\lambda=2,4,\dots$

I have definitely done something wrong here since e.g. $\lambda=2$ cannot work, but I cannot spot the mistake. Alternative ways are also welcome.

2

There are 2 best solutions below

0
On BEST ANSWER

You are correct that $t$ must be a multiple of $9$ and $\lambda$ must be even, but this actually only uses the third equation. You also have the condition that $r=\frac{55t}6$ is an integer, and this means $t$ also has to be a multiple of $6$, so $t$ is a multiple of $\operatorname{lcm}(9,6)=18$. (You also need the first equation to be satisfied, so $k=\frac{858r}{165}=\frac{143t}3$ has to be an integer, but that just means $t$ has to be a multiple of $3$, which you already know.)

Thus $t=18,36,...$ giving $\lambda=4,8,...$ (together with $0$ or negative values if they're allowed).

0
On

$\!\bmod 6\!:\ \ 0 \equiv 1287 \lambda \equiv 3 \lambda\iff 6\mid 3\lambda\iff 2\mid \lambda$

$\!\bmod 4\!:\ \ 0\equiv 165 \lambda\equiv \lambda\iff 4\mid \lambda$

$\!\bmod 2\!:\ \ 0\ \equiv\ 9\lambda\ \equiv\ \lambda\iff 2\mid \lambda$

So the system is equivalent to $\,2,4\mid \lambda\iff 4\mid \lambda$