2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – Samuele B. Mar 28 '20 at 16:14
  • 1
    $\begingroup$ @SamueleB. Yes for both questions. $\endgroup$ – Robert Z Mar 28 '20 at 16:19
  • $\begingroup$ @SamueleB. I added an answer which explains the actual mistake. $\endgroup$ – Bill Dubuque Mar 28 '20 at 19:07
  • 1
    $\begingroup$ @SamuleB I am happy that finally you understood the actual mistake. $\endgroup$ – Robert Z Mar 30 '20 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.