use the Euclidean algorthim to find a solution to $x$

Question

Use the Euclidean algorthim to find a solution to $x$ (in terms of $r$ and $s$) if $$x\equiv r \mod(28) \;\;\text{and}\;\;\; x\equiv s \mod(45).$$

Answer 1

Since $\gcd(28,45)=1$, it follows that there exist $m,n \in \Bbb Z$ such that $28m + 45n = 1$. Consider then $x = 28mr + 45ns$. Then

$$x = 28mr + 45ns = (1-45n)r + 45ns = r + 45(-nr+ns) \equiv r \pmod{45}$$

and

$$x = 28mr + 45ns = 28mr + (1-28m)s = s + 28(mr-ms) \equiv s \pmod{28} .$$

This solution is not unique because $x + 28 \cdot 45 k$ will also be a solution for every $k \in \Bbb Z$.

To concretely find $m$ and $n$ one usually uses the extended Euclidian algorithm: it will give $m = -8$ and $n=5$, therefore the solutions are $x = -224r + 225s + 1260k$ with $k \in \Bbb Z$ arbitrary.