Foundations: Division and Greatest Common Divisors

Explain the Division Algorithm and its role in establishing the structure of integers.

Define divisibility and prove its fundamental properties (e.g., transitivity, linearity).

Explain why the Euclidean Algorithm correctly computes the GCD of two integers.

Use the Extended Euclidean Algorithm to express the GCD of two integers as a linear combination of them (Bézout's Identity).

Prove and apply Euclid's Lemma (if a prime p divides ab, then p divides a or p divides b).

Define and compute the Least Common Multiple (LCM) and prove its relationship with the GCD.