ConceptSystems & CS
Greatest common divisor
The greatest common divisor of two numbers is the largest positive integer that divides both numbers without a remainder.
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.
Euclid's algorithm4Euclidean algorithm2Cesàro's method for pi1Euclidean algorithm (for rhythm)1Euler's phi function1Euler's theorem1Euler's totient function1Extended Euclidean algorithm1Extended GCD algorithm1Greatest common divisor reduction1Lemma 1 (GCD subtraction property)1Lowest terms fraction1
Lecturers
7Each in their own terms, from the easiest level.
Christof Paar
The largest integer that divides both given numbers without leaving a remainder.Ana Bell
A helper function used to find the largest positive integer that divides each of two integers without a remainder, used here to reduce fractions.Hal Abelson & Gerald Jay Sussman
A procedure that computes the greatest common divisor of two numbers, used here to reduce rational numbers to lowest terms.Eric Grimson
An algorithm used to find the greatest common divisor of two numbers in order to reduce fractions to their simplest terms.Tom Leighton
The greatest common divisor of two integers a and b is the largest integer that divides both a and b.Ankur Moitra
The greatest common divisor of a and b is the largest integer that divides both.
Lectures that assume it
10- Assignment, State, and Side-effects (SICP Lecture 5a)
- The RSA Cryptosystem and Efficient Exponentiation
- Register Machines (SICP Lecture 9a)
- Cryptography: Encryption
- Thinking Above the Code
- Shor's Factoring Algorithm
- Primes and Prime Fields
- Diffie-Hellman Key Exchange and the Discrete Log Problem
- Number Theory II
- Count Me In: How Mathematics Explains Music
Connections
26The lectures that define it or assume it, and the concepts next to it.
Concepts8
Show 2 moreShow fewer
Lectures18
- Compound Data Structures in SICP
- Data Abstraction
- Number Theory for PKC: Euclidean Algorithm, Euler's Phi Function & Euler's Theorem
- Python Class Methods: Decomposition and Abstraction
- Number Theory I
- Modular Arithmetic and Historical Ciphers
Show 12 moreShow fewer
- Modular Arithmetic
- 25 Years of Mathematical Thrills
- Assignment, State, and Side-effects (SICP Lecture 5a)
- The RSA Cryptosystem and Efficient Exponentiation
- Register Machines (SICP Lecture 9a)
- Cryptography: Encryption
- Thinking Above the Code
- Shor's Factoring Algorithm
- Primes and Prime Fields
- Diffie-Hellman Key Exchange and the Discrete Log Problem
- Number Theory II
- Count Me In: How Mathematics Explains Music