Greatest common divisor, least common multiple and the Euclidean algorithm

Subtracting a multiple of $b$ from $a$ cannot create or destroy a shared divisor with $b$: anything that measures both $a$ and $b$ must also measure the leftover $r=a-bq$, and vice versa.

Step 1 (Same common divisors). Let $d$ be any integer dividing both $a$ and $b$, so $a=dx$ and $b=dy$ for integers $x,y$. Then $r=a-bq=dx-dyq=d(x-yq)$, so $d\mid r$, meaning $d$ divides both $b$ and $r$. Conversely, if $d$ divides both $b$ and $r$, say $b=dy$ and $r=dz$, then $a=bq+r=dyq+dz=d(yq+z)$, so $d\mid a$, meaning $d$ divides both $a$ and $b$.

Step 2 (Equality of greatest common divisors). Because the pairs $(a,b)$ and $(b,r)$ have the exact same set of common divisors, they have the exact same maximum element: $\gcd(a,b)=\gcd(b,r)$.

Step 3 (Finite termination). Each division step produces a remainder satisfying $0\le r<b$, so the sequence of second entries $b > r_1 > r_2 > \cdots \ge 0$ is a strictly decreasing sequence of non-negative integers. Such a sequence can have at most $b$ steps before reaching $0$; at the step $\gcd(r_{k-1},r_k)=\gcd(r_k,0)=r_k$, the last nonzero remainder $r_k$ is $\gcd(a,b)$.

For each prime $p$, $\gcd(a,b)$ takes the smaller exponent of $p$ in $a,b$ while $\operatorname{lcm}(a,b)$ takes the larger exponent; adding the smaller and larger of two numbers always gives their sum.

Step 1. Write the prime factorizations of $a$ and $b$ over all primes $p$: $a=\prod_p p^{e_p}$ and $b=\prod_p p^{f_p}$, where $e_p,f_p\ge0$ and only finitely many exponents are nonzero.

Step 2. A positive integer $d=\prod_p p^{c_p}$ divides both $a$ and $b$ iff $c_p\le e_p$ and $c_p\le f_p$ for every $p$, so the largest such divisor chooses $c_p=\min(e_p,f_p)$: $\gcd(a,b)=\prod_p p^{\min(e_p,f_p)}$. Dual reasoning for common multiples chooses the smallest exponent at least as large as both, giving $\operatorname{lcm}(a,b)=\prod_p p^{\max(e_p,f_p)}$.

Step 3. For any two real numbers, $\min(e_p,f_p)+\max(e_p,f_p)=e_p+f_p$. Multiplying the two productsprime-by-prime therefore gives $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=\prod_p p^{\min(e_p,f_p)+\max(e_p,f_p)}=\prod_p p^{e_p+f_p}=\left(\prod_p p^{e_p}\right)\left(\prod_p p^{f_p}\right)=ab$.