Concept

Greatest common divisor

Related concepts (24)

Graph Chatbot

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.

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

Irreducible fraction

An irreducible fraction (or fraction in lowest terms, simplest form or reduced fraction) is a fraction in which the numerator and denominator are integers that have no other common divisors than 1 (and −1, when negative numbers are considered). In other words, a fraction a/b is irreducible if and only if a and b are coprime, that is, if a and b have a greatest common divisor of 1. In higher mathematics, "irreducible fraction" may also refer to rational fractions such that the numerator and the denominator are coprime polynomials.

Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor.

Bézout domain

In mathematics, a Bézout domain is a form of a Prüfer domain. It is an integral domain in which the sum of two principal ideals is again a principal ideal. This means that for every pair of elements a Bézout identity holds, and that every finitely generated ideal is principal. Any principal ideal domain (PID) is a Bézout domain, but a Bézout domain need not be a Noetherian ring, so it could have non-finitely generated ideals (which obviously excludes being a PID); if so, it is not a unique factorization domain (UFD), but still is a GCD domain.