Wolfram Researchfunctions.wolfram.comOther Wolfram Sites
Search Site
Function CategoriesGraphics GalleryNotationsGeneral IdentitiesAbout This Site Email Comments

View Related Information In
The Documentation Center
MathWorld

Download All Formulas For This Function
Mathematica Notebook
PDF File

Download All Introductions For This Function
Mathematica Notebook
PDF File

 

Developed with Mathematica -- Download a Free Trial Version
 











ExtendedGCD






Mathematica Notation

Traditional Notation









Integer Functions > ExtendedGCD[n1,n2,...,nm] > Introduction to the GCD and LCM (greatest common divisor and least common multiple)





Definitions of GCD and LCM

The GCD and LCM group of functions includes the following three functions: • the greatest common divisor (gcd): • the least common multiple (lcm): • the extended greatest common divisor (egcd):

These functions are defined in the following ways:

is the greatest common divisor of the integers (or rational) . It is the greatest integer factor common to all the .

is the least common multiple of the integers (or rational) . It is the minimal positive integer that divides all the .

is the extended greatest common divisor of the integers . In particular,

Examples: The greatest common divisor of 21 and 48, is 3. Similar examples are , , . The least common multiple of the three numbers 2, 4, and 5, is . Similar examples are , , . The extended greatest common divisor of 21 and 48 is because the greatest common divisor and . Similarly, .