Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

The Greatest Common Divisor

Description

This lecture covers the concept of the greatest common divisor (gcd), including the Euclidean algorithm and Joseph Stein's algorithm. It explains how to determine if a number divides another and provides demonstrations of the gcd calculation. The lecture also explores special cases for even and odd numbers, as well as practical examples.

In MOOCs (2)

Analysis I (part 1): Prelude, basic concepts, real numbers

Analysis I

Official source

Quiz

Related concepts (14)

Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use.

Number theory

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example, rational numbers), or defined as generalizations of the integers (for example, algebraic integers).

Algebraic number theory

Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic objects such as algebraic number fields and their rings of integers, finite fields, and function fields. These properties, such as whether a ring admits unique factorization, the behavior of ideals, and the Galois groups of fields, can resolve questions of primary importance in number theory, like the existence of solutions to Diophantine equations.

Euclidean domain

In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements.

GCD domain

In mathematics, a GCD domain is an integral domain R with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated by two given elements. Equivalently, any two elements of R have a least common multiple (LCM). A GCD domain generalizes a unique factorization domain (UFD) to a non-Noetherian setting in the following sense: an integral domain is a UFD if and only if it is a GCD domain satisfying the ascending chain condition on principal ideals (and in particular if it is Noetherian).

Related lectures (29)

Polynomials: Roots and Factorization

Explores polynomial roots, factorization, and the Euclidean algorithm in depth.

Number Theory: Quiz

Covers fundamental concepts in number theory with examples and quizzes.

Euclid and Bézout: Algorithms and Theorems

Explores the Euclidean algorithm, Bézout's identity, extended Euclid algorithm, and commutative groups in mathematics.

Number Theory: GCD and LCM

Covers GCD, LCM, and the Euclidean algorithm for efficient computation of GCD.