What is the best way to solve a problem given remainders and divisors? $x$ is a positive integer less than $100$.  When $x$ is divided by $5$, its remainder is $4$.  When $x$ is divided by $23$, its remainder is $7$.  What is $x$ ?
 A: What we have here is a system of congruences of the form $x \equiv r_i \pmod{p_i}$ with $p_i$ being the primes $5, 23$ and $r_i$ the remainders $4, 7$.
The general method is based on a theorem Chinese remaindering. That is $\Bbb{Z}/115\Bbb{Z} \cong \Bbb{Z}/5\Bbb{Z} \times \Bbb{Z}/23\Bbb{Z}.$
Using the steps in the Wikipedia page for Chinese remaindering algorithm. We have the system $$ x \equiv 4 \pmod{5} \\ x \equiv 7 \pmod{23}$$
where $5, 23$ are coprimes. Let $M = 5\cdot 23 = 115.$ Our goal is to find $x \pmod{M}.$
First run the extended Euclidean algorithm on $5$ and $23$ to get
$$ 5\times (-9) + 23\times 2  = 1 $$
Let $e_1 = 23\times 2 = 46$ and $e_2 = 5\times (-9) = -45.$ Then the solution to the system above is given by $$ x = 4 e_1 + 7 e_2 = -131 \equiv 99 \pmod{115}.$$
So the solution is $x = 99.$
A: So, $x=5y+4$ and $x=23z+7$  for some integers $y,z$
So, $5y+4=23z+7=>5y+20=23z+23$ adding 16 to either sides,
$5(y+4)=23(z+1)=>y+4=\frac{23(z+1)}{5}$, so,$5|(z+1)$  as $y+4$ is integer and $(5,23)=1$
$=>z+1=5w$ for some integer $w$.
$x=23(5w-1)+7=115w-16$
As $0<x<100$ so,$x=99$ putting $w=1$

Alternatively, We have $5y=23z+3$
Using convergent property of continued fractions,
(i)$\frac{23}{5}=4+\frac{3}{5}=4+\frac{1}{\frac{5}{3}}=4+\frac{1}{1+\frac{2}{3}}$
$=4+\frac{1}{1+\frac{1}{\frac{3}{2}}}=4+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}$
So, the last but one convergent is $4+\frac{1}{1+\frac{1}{1}}=\frac{9}{2}$
$=>23\cdot2-5\cdot9=1$
$5y=23z+3(23\cdot2-5\cdot9)=>5(y+27)=23(z+6)=>5|(z+6)=>5|(z+1)$
(ii)$\frac{23}{5}=4+\frac{3}{5}=4+\frac{1}{\frac{5}{3}}=4+\frac{1}{1+\frac{2}{3}}$
$=4+\frac{1}{1+\frac{1}{\frac{3}{2}}}=4+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}$
$=4+\frac{1}{1+\frac{1}{1+\frac{1}{1+1}}}$
So, the last convergent is $4+\frac{1}{1+\frac{1}{1+1}}=\frac{14}{3}$
$=>23\cdot3-5\cdot14=-1$
$5y=23z-3(23\cdot3-5\cdot14)=5(y-42)=23(z-9)=>5|(z-9)=>5|(z+1)$
