find the least positive integer x satisfying both 3x≡11 (mod 17) and 5x≡9 (mod 23)

Question

Q.find the least positive integer x satisfying both 3x≡11 (mod 17) and 5x≡9 (mod 23)

How to solve problems like this? Using CRT theorem?

Answer 1

There are various methods. The following uses your problem to illustrate one approach.

Here with coprime moduli and solvable congruences (moduli are prime, so everything has a multiplicative inverse) CRT guarantees one solution modulo $17\times 23=(20-3)(20+3)=400-9=391$.

It is easiest, I think, to reduce to a standard form, noting that $3\times 6=18\equiv 1 \bmod 17$ and $5\times 14=70 \equiv 1\bmod 23$ so multiply the first by $6$ and the second by $14$ obtaining $$x\equiv 66\equiv 15\equiv-2\bmod 17$$ (don't be afraid of introducing negative numbers into the computations if it keeps the arithmetic easy) and $$x\equiv 126\equiv 11\bmod 23$$

These can be combined as $$x=17a-2=23b+11$$Now we echo the Euclidean algorithm, adding extra variables, but taking care to reduce the coefficients. First set $c=a-b$ which gives $$17c=6b+13$$Then $d=b-2c$ so that $$5c=6d+13$$ and with $e=c-d$ we have $$5e=d+13$$

Here we have $d=2, e=3$ then $c=5, b=12,a=17$

Answer 2

Given \begin{align} &x\equiv\frac{11}3\pmod{17}& &x\equiv\frac 95\pmod{23} \end{align} we have \begin{align} &\frac{11}{3\cdot\color{orange}{23}}\equiv\color{red}{11}\pmod{\color{green}{17}}& &\frac{9}{5\cdot\color{green}{17}}\equiv\color{blue}{2}\pmod{\color{orange}{23}} \end{align} hence \begin{align} x\equiv\color{red}{11}\cdot\color{orange}{23}+\color{blue}{2}\cdot \color{green}{17}=287\pmod{\color{green}{17}\cdot\color{orange}{23}} \end{align} is the smallest solution.