System of two congruence equations

Question

How can I solve this system?

$$ \left\{ \begin{array}{c} 9x \equiv 5 \pmod{10} \\ 14x \equiv 8 \pmod{18} \\ \end{array} \right. $$

Answer 1

You have to simplify this system to a system of congruences in the form $x\equiv a_i \pmod{m_i}$, where the moduli $m_i$ are coprime.

Namely, since $9$ is a unit mod. $1$, with inverse $9$, the first congruence is equivalent to $$ x\equiv 9\cdot 5\equiv 5\pmod{10}. $$

The second congruence is equivalent to $$7x\equiv 4\pmod 9,$$ and as the inverse of $7$ mod. $9$ is $4$, it is in turn equivalent to $$x\equiv 4\cdot 4\equiv 7\pmod 9.$$ Can you take it from here?

Answer 2

writing your equations in the form $$9x=5+10m$$ $$14x=8+18n$$ then you will get by eliminating $x$ $$7m-81n=1$$ solving this Diophantine equation we obtain $$m=58+81C,n=57+7C$$ where $C$ is a constant from the first equation we get $$x=\frac{5}{9}+\frac{10}{9}m$$ and from here we obtain $$14\left(\frac{5}{9}+\frac{10}{9}m\right)=8+18n$$ etc

Answer 3

We have $$9x\equiv5\equiv45\pmod{10}\implies x\equiv5\pmod{10}$$ and $$14x\equiv8\pmod{18}\implies7x\equiv4\equiv49 \pmod9\implies x\equiv7\pmod9$$ by the Cancellation Rule.

Now for the first congruence, $$x=5, 15, 25, ...$$ and since $25\equiv7\pmod9$, the solution is $$\boxed{x\equiv25\pmod{90}}$$

Answer 4

$9x\equiv_{10}5$, multiply both sides by $9$ to get $81x\equiv_{10}x\equiv_{10}45\equiv_{10}5$, so $x\equiv_{10}5$

$14x\equiv_{18}8$, this is the same as solving $7x\equiv_9 4$, mutiply by $4$ on both sides to get $28x\equiv_{9}x\equiv_9 16\equiv_9 7$, so $x\equiv_9 7$.

This yields $x\equiv_{90}25$

Answer 5

The plan: Solve each linear congruence equation individually, then combine the results using the Chinese Remainder Theorem.

Solve the first linear congruence equation using the modular multiplicative inverse of $9$:

$9x\equiv 5 \bmod 10 \\ \text{Since }9\cdot 9= 81\equiv 1 \bmod 10, \quad 9^{-1}\equiv 9 \bmod 10 \\ 9\cdot 9x\equiv 9\cdot5 \bmod 10 \\ x\equiv 9\cdot5\equiv 45\equiv 5 \bmod 10 \\ $

The second linear congruence equation needs a factor of two taken out from coefficients and modulus before it can be solved similarly:

$14x\equiv 8 \bmod 18 \\ \Rightarrow 7x \equiv 4\bmod 9$

The reason is clear if the relationship is expressed as $14x=8+18k$, since then it is clear that $7x=4+9k$ is also true.

Now we have $\gcd(7,9)=1$ we will be able to find a modular inverse:

$9x\equiv 5 \bmod 10 \\ \text{Since }7\cdot 4= 28\equiv 1 \bmod 9, \quad 7^{-1}\equiv 4 \bmod 9 \\ 4\cdot 7x\equiv 4\cdot4 \bmod 9 \\ x\equiv 4\cdot4\equiv 16\equiv 7 \bmod 9 \\ $

So we have
$\begin{cases} x\equiv 5 \bmod 10 \\ x\equiv 7 \bmod 9 \\ \end{cases}$

Since $\gcd(10,9)=1$, the Chinese remainder theorem tells us there will be a solution to this system modulo $10\cdot 9=90$.

A simple search of values qualifying as $5\bmod 10$: $5,15,25,\ldots$ gives us $x\equiv 25\bmod 90$.