Elementary Number Theory · Number
Divisibility and the Euclidean Algorithm
The Euclidean algorithm computes the GCD in logarithmic time. Bézout’s identity says the GCD can always be written as ax + by.
WHAT STUDENTS WILL LEARN
✓Define divisibility; prove basic properties
✓Apply the division algorithm
✓Compute GCD using the Euclidean algorithm
✓Express gcd(a,b) as a linear combination (Bézout)
COURSE OUTLINE · CLICK A PART FOR RESOURCES