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

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?

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

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}$$.

• Thank you! From a perspective of finding the mistake, can we say that my error was solving the diophantine equation without having first reduced it dividing everything by $2$? Is it mandatory to make sure the associated equation is always reduced? Mar 28, 2020 at 16:14
• @SamueleB. Yes for both questions. Mar 28, 2020 at 16:19
• @SamueleB. I added an answer which explains the actual mistake. Mar 28, 2020 at 19:07
• @SamuleB I am happy that finally you understood the actual mistake. Mar 30, 2020 at 12:56