Sign inSign in
ConceptSystems & CS

Euclid's algorithm

An ancient algorithm for computing the greatest common divisor of two numbers.
as Hal Abelson & Gerald Jay Sussman defines itMITThe wording closest to all 4 definitions
Watch it explained

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.

Greatest common divisor4Division lemma1Division theorem1Inequalities1Natural numbers1

Opens up

Concepts that name this one as a prerequisite.

Lecturers

4

Each in their own terms, from the easiest level.

  • Leslie Lamport

    Microsoft Research · Undergraduate

    An algorithm that computes the greatest common divisor of two natural numbers M and N by iteratively subtracting the smaller from the larger until they are equal.
    • 11:50Thinking Above the Code
  • Tom Leighton

    MIT · Undergraduate

    An algorithm for computing the greatest common divisor of two integers, also referred to as the pulverizer.
  • Edsger W. Dijkstra

    UT Austin · Undergraduate

    An algorithm for computing the greatest common divisor of two integers by repeatedly subtracting or taking the remainder.
    • 18:2425 Years of Mathematical Thrills

Lectures that assume it

1

Connections

8

The lectures that define it or assume it, and the concepts next to it.

Concepts3

Lectures5

4 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.