Albarellak

2021-01-31

Find the smallest positive integer solution to the following system of congruences:
$x\equiv 17\left(\text{mod}35\right)$
$x\equiv 8\left(\text{mod}43\right)$

lamusesamuset

Given,
$x\equiv 17\left(\text{mod}35\right)$
and
$x\equiv 8\left(\text{mod}43\right)$
Step 2
Now x = 17 + 35k, for some $k\in \mathbb{Z}$
Then,
$17+35k\equiv 8\left(\text{mod}43\right)$
$35k\equiv -9\left(\text{mod}43\right)$
$35k\equiv 34\left(\text{mod}43\right)$
$⇒gcd\left(35,43\right)=1$
Then, there exists x,$y\in \mathbb{Z}$ such that 35x + 43y = 1
$\because 35=4×8+3$
$43=35×1+8$
$8=3×2+2$
Step 3
$3=2×1+1$
$⇒1=3-2×1$
$⇒1=3-\left(8-3×2\right)×1$
$⇒1=3×3-8×1$
$⇒1=3×\left(35-4×8\right)-8×1$
$⇒1=3×35-8×13$
$⇒1=3×35-\left(43-35×1\right)×13$
$⇒1=16×35-43×13$
$⇒1=35\left(16\right)+43\left(-13\right)$
Hence, x = 16

Do you have a similar question?