2
$\begingroup$

$$6x \equiv 2 \pmod 4 \\ 4x \equiv 6 \pmod 9 \\ x \equiv 15 \pmod {17}$$ I need to find a minimal solution for this system. Ideally, I want to use CRT but it can't be done because the LHS's aren't the same. I tried to simplify the equations but I didn't see where it lead.

I'd be glad for help

Thanks!

$\endgroup$
1
$\begingroup$

It is possible to remove the multipliers on the LHSs. For the first equation, note that it is equivalent to $$2x\equiv2\bmod4$$ $$x\equiv1\bmod2$$ For the second, 4 has an inverse modulo 9, so multiply by that inverse on both sides: $$x\equiv7\cdot6\equiv6\bmod9$$ Now the CRT can be applied, yielding a minimal solution of 15.

$\endgroup$
2
$\begingroup$

Consider the system : $$\begin{cases}6x \equiv 2 \pmod 4 \\ 4x \equiv 6 \pmod 9 \\ x \equiv 15 \pmod {17}\end{cases}$$

Solve each congruence separately and you get: $$\begin{cases}x \equiv 1 \pmod 2 \\ x \equiv 6 \pmod 9 \\ x \equiv 15 \pmod {17}\end{cases}$$

Then apply the Chinese Remainder Theorem and you get the solution: $$x \equiv 15 \pmod {306}$$

$\endgroup$
1
$\begingroup$

from the last equation we get $$x=15+17m$$ and the second one $$4x=6+9n$$ with $$m,n \in\mathbb{Z}$$ eliminating $x$ we get $$68m=9n-54$$ this is a linear Diophantine equation with the solution set $$m=9k,n=6+68k$$ and we can compute $$x=15+153k$$ and then we can check the first equation: $$6\cdot x=90+918k\equiv 2 \mod 4$$

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