Sign inSign in
ConceptSystems & CS

Greatest common divisor

The greatest common divisor of two numbers is the largest positive integer that divides both numbers without a remainder.
as Edsger W. Dijkstra defines itUT AustinThe wording closest to all 8 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.

Divisibility5Integer3Arithmetic operations1Function1Integer division1Primitive operators1Procedure1Recursion1

Opens up

Concepts that name this one as a prerequisite.

Lecturers

7

Each in their own terms, from the easiest level.

  • Christof Paar

    Ruhr University Bochum · Introductory

    The largest integer that divides both given numbers without leaving a remainder.
    • 4:21Number Theory for PKC: Euclidean Algorithm, Euler's Phi Function & Euler's Theorem
    • 1:10:20Modular Arithmetic and Historical Ciphers
  • Ana Bell

    MIT · Introductory

    A helper function used to find the largest positive integer that divides each of two integers without a remainder, used here to reduce fractions.
    • 1:07:39Python Class Methods: Decomposition and Abstraction
  • Hal Abelson & Gerald Jay Sussman

    MIT · Undergraduate

    A procedure that computes the greatest common divisor of two numbers, used here to reduce rational numbers to lowest terms.
    • 28:13Compound Data Structures in SICP
  • Eric Grimson

    MIT · Undergraduate

    An algorithm used to find the greatest common divisor of two numbers in order to reduce fractions to their simplest terms.
  • Tom Leighton

    MIT · Undergraduate

    The greatest common divisor of two integers a and b is the largest integer that divides both a and b.
  • Ankur Moitra

    MIT · Undergraduate

    The greatest common divisor of a and b is the largest integer that divides both.

Lectures that assume it

10

Connections

26

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

7 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.