Greatest Common Divisors and the Euclidean Algorithm
The greatest common divisor of integers $a$ and $b$, not both zero, is the greatest positive integer dividing both.
Summary
The greatest common divisor of integers and , not both zero, is the greatest positive integer dividing both. The Euclidean algorithm computes it efficiently without enumerating divisors.
Euclidean division writes , where . Replacing with preserves all common divisors, so . Repeated updates terminate because the nonnegative remainders strictly decrease. When the second entry becomes zero, the first entry's absolute value is the GCD.
🧠 Key Concepts
- Greatest Common Divisor
- Euclidean Division
- Common Divisor Invariant
- Algorithm Termination
- Bézout Coefficients
- Coprime Integers
- Modular Inverses
- Worst Case Complexity
🧠 Quick Check
See what you remember from the summary.
Which best describes why replacing an integer pair with its smaller entry and division remainder preserves the GCD?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Greatest Common Divisors and the Euclidean Algorithm
📘 Overview The Euclidean algorithm computes the greatest common divisor by repeatedly replacing a pair of integers with the smaller integer and their division remainder. Its extended form also finds integer coefficients used to compute modular inverses.
🧠 Key Idea Taking a remainder preserves common divisors:
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🌱 BSCS Year 1 — Computing & College Foundations
Browse this Review Set →More Computer Engineering notes
See all →More in Discrete Mathematics
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.