1
$\begingroup$

\begin{align*} x & \equiv 12 \pmod{25}\\ x & \equiv 2 \pmod{30} \end{align*}

Hi guys, I'm not sure how to attack this problem. I know how to solve it if the moduli are coprime, but that doesn't work in this instance. Is there some other method I'm not familiar with that can be used or is this unsolvable?

Perhaps there is some way to manipulate the congruences to make the moduli prime and then solve by the standard CRT method? Thanks for you help!

$\endgroup$
3
$\begingroup$

Any solution of the first is congruent to $2$ modulo $5$. The second congruence can be written as $x\equiv 2\pmod{5}$ and $x\equiv 2\pmod{6}$. So we need only solve the system $x\equiv 12\pmod{25}$, $x\equiv 2\pmod{6}$. Now the moduli are relatively prime.

$\endgroup$
3
$\begingroup$

${\rm mod}\ 30:\ x\equiv 2\iff x = 2+30n$

${\rm mod}\ 25\!:\ 12\equiv x\equiv 2+30n\equiv 2+5n\iff 5n\equiv 10$

But $\ 25\mid 5n-10 \overset{\ \ {\rm cancel}\ 5}\iff 5\mid n-2\iff \color{#c00}n\equiv 2+5k$

Thus $\ x = 2+30\,\color{#c00}n = 2+30(2+5k)= 62+150k$

$\endgroup$

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.