Lecture

The Greatest Common Divisor

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

This course covers : Part 1: Prelude, basic concepts, real numbers. Part 2: Introduction to complex numbers. Part 3: Real number sequences I and II. Part 4: Limit of a function, continuous functions. Part 5: Continuous functions and derivable functions, the derivative function. Part 6: Studies of functions, limited developments. Part 7: Indefinite and definite integrals, integration (selected chapters).

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

Can you calculate the value of sin(π/4)? Does the identity ln(xy)=ln(x)+ln(y) sound familiar? In the prelude we recall and expand on a few such notions, in particular the trigonometric functions sin, cos and tan and their properties, the concept of reciprocal functions such as exp and ln, some calculation rules concerning powers, logarithms and roots, sets and functions. Next we discuss number systems: based on the "intuitive" notion of the natural integers N={0,1,2,3,...}, we rigorously define the rational

Official source

Quiz

Related concepts (15)

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 (38)

Polynomials: Roots and Factorization

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

Polynomial Factorization over Finite Fields

Introduces polynomial factorization over finite fields and efficient computation of greatest common divisors of polynomials.

Number Theory: Quiz

Covers fundamental concepts in number theory with examples and quizzes.

Number Theory: Division, Remainder, Congruence

Covers number theory, division, remainder, congruence, prime numbers, integer representation, and the Euclidean algorithm.

Integers: Well Ordering and Induction