ConceptMathematics
Euclidean algorithm
An iterative, reductive algorithm used to compute the greatest common divisor of two integers without needing their prime factorizations.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ankur Moitra
An efficient algorithm for computing the greatest common divisor of two integers by repeatedly applying the division algorithm and replacing the larger number with its remainder.
Lectures that assume it
5Connections
15The lectures that define it or assume it, and the concepts next to it.
Concepts8
- Greatest common divisor
- Division algorithm
- Integer division with remainder
- Extended Euclidean algorithm
- Binary Euclidean algorithm
- Chinese remainder theorem