Question: User: b) Given a = 252 and b = 198, use the Euclidean algorithm to solve the Greatest Common Divisor (GCD) of a and b and present it in the form of $sa + tb$, where $s, t \in \mathbb{Z}$. Hence, compute the Least Common Multiple (LCM) of 252 and 198.
1. **State the problem:** Find the GCD of $a=252$ and $b=198$ using the Euclidean algorithm and express it as $sa + tb$ where $s,t \in \mathbb{Z}$. Then find the LCM of 252 and 198.
2. **Euclidean algorithm to find GCD:**
We repeatedly apply the division algorithm:
$$252 = 198 \times 1 + 54$$
$$198 = 54 \times 3 + 36$$
$$54 = 36 \times 1 + 18$$
$$36 = 18 \times 2 + 0$$
Since the remainder is now 0, the GCD is the last nonzero remainder:
$$\gcd(252,198) = 18$$
3. **Express GCD as $sa + tb$ (Extended Euclidean algorithm):**
Start from the second last equation:
$$18 = 54 - 36 \times 1$$
Substitute $36$ from the previous step:
$$36 = 198 - 54 \times 3$$
So,
$$18 = 54 - (198 - 54 \times 3) = 54 \times 4 - 198$$
Substitute $54$ from the first step:
$$54 = 252 - 198 \times 1$$
So,
$$18 = (252 - 198) \times 4 - 198 = 252 \times 4 - 198 \times 5$$
Thus,
$$s = 4, \quad t = -5$$
4. **Compute LCM:**
Recall the relation:
$$\mathrm{LCM}(a,b) = \frac{|a \times b|}{\gcd(a,b)}$$
Calculate:
$$\mathrm{LCM}(252,198) = \frac{252 \times 198}{18}$$
Simplify:
$$= \frac{252 \times 198}{\cancel{18}} = 252 \times \frac{198}{\cancel{18}} = 252 \times 11 = 2772$$
**Final answers:**
- $\gcd(252,198) = 18 = 4 \times 252 - 5 \times 198$
- $\mathrm{LCM}(252,198) = 2772$