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

2,062

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$

Share:
2,062

Related videos on Youtube

Edward
Author by

Edward

Updated on January 15, 2023

Comments

  • Edward
    Edward 10 months

    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?

    • mvw
      mvw about 5 years
      Chinese remainder theorem is for solving simultaneous congruences.
  • Edward
    Edward about 5 years
    Thanks for your reply, I am confused of the using 11/3*23 and 9/5*17 what does it means?
  • Fabio Lucchini
    Fabio Lucchini about 5 years
    You can divide by integers coprime to the modulus.