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?
Best Answer
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}$