GCD, LCM and the Euclidean Algorithm

A floor measuring $180$ cm by $48$ cm is to be covered with equal square tiles, without cutting any. How large can the tiles be? A side $s$ works exactly when whole tiles fill both edges, that is, when $s \mid 180$ and $s \mid 48$. So the largest $s$ is $\gcd(180, 48)$. With $180 = 2^2\cdot3^2\cdot5$ and $48 = 2^4\cdot3$, the minimum exponents give $2^2\cdot3 = 12$. The floor takes $15\times4 = 60$ tiles of $12$ cm.

What values can $\gcd(n, n + 6)$ take for positive integers $n$? Any common divisor of $n$ and $n + 6$ divides their difference $6$, so the gcd is one of $1, 2, 3, 6$. All four occur: $\gcd(1, 7) = 1$, $\gcd(2, 8) = 2$, $\gcd(3, 9) = 3$, $\gcd(6, 12) = 6$. The same difference trick shows that consecutive integers are always coprime.

Divide, then divide the divisor by the remainder: $252 = 2\cdot105 + 42$; $105 = 2\cdot42 + 21$; $42 = 2\cdot21 + 0$. The pairs $(252, 105)$, $(105, 42)$, $(42, 21)$ all have the same gcd, and the last one is obviously $21$. So $\gcd(252, 105) = 21$ — three divisions, no factoring.

Show $\gcd(5n + 3, 3n + 2) = 1$ for every integer $n$. Subtract to shrink, exactly as the algorithm does: $\gcd(5n + 3, 3n + 2) = \gcd(3n + 2, 2n + 1) = \gcd(2n + 1, n + 1) = \gcd(n + 1, n) = \gcd(n, 1) = 1$. Each step replaces the larger expression by its difference with the smaller, which keeps the gcd, until a constant is reached.

Find $\gcd(2^{18} - 1, 2^{12} - 1)$. Divide: $2^{18} - 1 = 2^6(2^{12} - 1) + (2^6 - 1)$, so the gcd equals $\gcd(2^{12} - 1, 2^6 - 1)$. And $2^{12} - 1 = (2^6 - 1)(2^6 + 1)$ is a multiple of $2^6 - 1$, so the gcd is $2^6 - 1 = 63$. The exponents ran through Euclid's algorithm themselves: $\gcd(18, 12) = 6$, and in general $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m, n)} - 1$.

From $252 = 2\cdot105 + 42$ and $105 = 2\cdot42 + 21$: start from the last useful line, $21 = 105 - 2\cdot42$, then replace $42$ using the line above it, $42 = 252 - 2\cdot105$: $21 = 105 - 2(252 - 2\cdot105) = 5\cdot105 - 2\cdot252$. Check: $525 - 504 = 21$.

With a $9$-litre jug, a $4$-litre jug and a tap, can you measure exactly $1$ litre? Bézout says yes, because $\gcd(9, 4) = 1$, and it tells you how: $1 = 9 - 2\cdot4$. Fill the $9$-litre jug, pour from it into the $4$-litre jug twice (emptying the small jug in between), and $1$ litre is left. Any whole number of litres up to $9$ can be reached the same way.

Which integers can be written as $84x + 126y$ with $x, y$ integers? Every such number is a multiple of $\gcd(84, 126) = 42$, since $42$ divides both terms. Conversely $42 = 2\cdot84 - 126$ is itself of this form, so every multiple $42m = 84(2m) + 126(-m)$ is too. The reachable totals are exactly the multiples of $42$; for example $100$ is not reachable.

Find $\text{lcm}(252, 105)$. With the gcd already known, $\text{lcm} = 252\cdot105/21 = 1260$. Check by factoring: $252 = 2^2\cdot3^2\cdot7$ and $105 = 3\cdot5\cdot7$; the maximum exponents give $2^2\cdot3^2\cdot5\cdot7 = 1260$.

Three bells ring every $12$, $18$ and $30$ minutes, and all ring together at noon. When do they next ring together? The minutes that work are the common multiples of $12$, $18$, $30$; the first is their lcm. From $12 = 2^2\cdot3$, $18 = 2\cdot3^2$, $30 = 2\cdot3\cdot5$, the maximum exponents give $2^2\cdot3^2\cdot5 = 180$ minutes: at $3$ p.m.

How many pairs $a \le b$ have $\gcd = 6$ and $\text{lcm} = 180$? Write $a = 6a\prime$, $b = 6b\prime$ with $\gcd(a\prime, b\prime) = 1$. Then $\text{lcm} = 6a\prime b\prime = 180$, so $a\prime b\prime = 30 = 2\cdot3\cdot5$ with coprime factors: each of the three primes goes wholly to $a\prime$ or to $b\prime$. That is $2^3 = 8$ ordered splits, $4$ unordered: $(6, 180), (12, 90), (18, 60), (30, 36)$.