Wrong solution of congruence system due to not cancelling gcd in homogeneous solution

Question

I have the following system of congruences:

$$\cases{3x\equiv6\pmod{18}\\2^x \equiv1\pmod5}$$

After solving the two equations, I obtain: $$\cases{x\equiv2\pmod6\\x\equiv0\pmod4}$$ As per the Chinese remainder theorem, I expect the solution to be in the form $x\equiv x_0\pmod{12}$, however the following procedure, which is the one we've been taught at my course, leads to a result modulo $24$.

$$x\equiv2\pmod6 \land x\equiv0\pmod4 \iff x = 2 + 6k = 4h$$$$ k, h \in \mathbb{Z}$$

So we have the equation $$6k-4h = -2$$ which $k_0 = -1, h_0 = -1$ are a particular solution of. Therefore, $k = -1 +4y, h = -1 + 6y$, with $y \in \mathbb{Z}$.

Plugging, say, the equation for $k$ back into our equation for $x$, I get $x = 2 + 6(-1+4y) = 2 - 6 + 24y$, which means $x\equiv-4\pmod{24}$.

However, I was expecting an answer modulo $12$. What am I missing?

Answer 1

The mistake is that you didn't cancel $\,\color{#c00}{\gcd(4,6)=2}\,$ in the homogenous component of the solution. Recall that the general solution of a linear equation like $\,4h-6k = 2\,$ is the sum of any particular solution plus the general solution of the associated $\rm\color{#0a0}{homogeneous}$ equation, here $\, 4h - 6k \color{#0a0}{= 0},\,$ with homogeneous general solution $\ \dfrac{h}k = \color{#c00}{\dfrac{6}4}^{\phantom{|^{|^|}}}\!\!\!\! = \dfrac{3}2\iff \begin{align}h=3n\\ k = 2n\end{align}\qquad$

So the general solution is $\,(h,k) =\underbrace{(-1,-1)+(3n,2n)}_{\rm particular \ +\ homogeneous\!\!\!\!\!} = (-1\!+\!3n,\,-1\!+\!2n)$

thus we conclude that $\, x = 4h = 4(-1\!+\!3n)=-4\!+\!12n\equiv 8\pmod{\!12}$

Answer 2

From your work, $6k-4h = -2$ is equivalent to $2h-3k=1$ and then we find $h=-1+3y$, and $k=-1+2y$ with $y \in \mathbb{Z}$. Hence $$x = 4(-1+3y)=-4+12y$$ that is $x\equiv 8\pmod{12}$.

A slight different approach. Note that $\gcd(6,4)=2$ and therefore $$\cases{x\equiv2\pmod6\\x\equiv0\pmod4}\Leftrightarrow \cases{z\equiv1\pmod3\\z\equiv0\pmod2}$$ where $x=2z$. The equivalent system on the right is solved by $z\equiv 4\pmod{6}$ and therefore, going back to $x$, we find that $x\equiv 8\pmod{12}$.