Question

find the least positive integer x such that x=5 (mod 7), x=7 (mod 11), x=3 (mod 13)?​

Answer 1

Answer:

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×23=(20−3)(20+3)=400−9=391.

It is easiest, I think, to reduce to a standard form, noting that 3×6=18≡1mod17 and 5×14=70≡1mod23 so multiply the first by 6 and the second by 14 obtaining

x≡66≡15≡−2mod17

(don't be afraid of introducing negative numbers into the computations if it keeps the arithmetic easy) and

x≡126≡11mod23

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