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