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): ![](/IntegerFunctions/ExtendedGCD/introductions/GCDandLCM/02/imagetext/0003/text03.gif)
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, ![](/IntegerFunctions/ExtendedGCD/introductions/GCDandLCM/02/imagetext/0017/text17.gif)
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, .
|