Find the smallest positive integer solution to the following system of congruences: x≡17(mod35) x≡8(mod43)

Question

Find the smallest positive integer solution to the following system of congruences:  x≡17(mod35)  x≡8(mod43)

lamusesamuset · Accepted Answer

Given,  x≡17(mod35)  and  x≡8(mod43)  Step 2  Now x = 17 + 35k, for some k∈Z  Then,  17+35k≡8(mod43)  35k≡−9(mod43)  35k≡34(mod43)  ⇒gcd(35,43)=1  Then, there exists x,y∈Z such that 35x + 43y = 1  ∵35=4×8+3  43=35×1+8  8=3×2+2  Step 3  3=2×1+1  ⇒1=3−2×1  ⇒1=3−(8−3×2)×1  ⇒1=3×3−8×1  ⇒1=3×(35−4×8)−8×1  ⇒1=3×35−8×13  ⇒1=3×35−(43−35×1)×13  ⇒1=16×35−43×13  ⇒1=35(16)+43(−13)  Hence, x = 16

Find the smallest positive integer solution to the following system of congruences: x≡17(mod35) x≡8(mod43)

Answered question

Answer & Explanation