GCD and LCM of 48 and 18

The smaller input need not be the GCD, and the larger need not be the LCM

The greatest common divisor, or GCD, is the greatest positive integer that divides both numbers with no remainder. For 48 and 18, the common divisors include 1, 2, 3 and 6. The greatest one is 6, so GCD(48, 18) = 6.

The least common multiple, or LCM, is the least positive integer that both numbers divide with no remainder. Multiples of 48 include 48, 96 and 144. Multiples of 18 include 18, 36, 54, 72, 90, 108, 126 and 144. Their first shared multiple is 144, so LCM(48, 18) = 144.

Replacing the larger value by the remainder keeps the GCD unchanged

Euclid's algorithm finds the GCD by repeatedly replacing the larger value with the remainder from dividing it by the smaller value. Start with 48 and 18. Since 48 = 2 * 18 + 12, the pair becomes 18 and 12. Then 18 = 1 * 12 + 6, so the pair becomes 12 and 6. Finally, 12 = 2 * 6 + 0, so the pair becomes 6 and 0.

The last nonzero value is 6. Every common divisor of the original pair is also a common divisor after each replacement, so this process does not change the GCD. When the second value reaches zero, the first value is the GCD.

Once the GCD is known, one division and one multiplication give the LCM

For two positive integers, the product of the GCD and LCM equals the product of the original inputs: GCD(48, 18) * LCM(48, 18) = 48 * 18. With the GCD equal to 6, rearrange the equation to get LCM(48, 18) = 48 / 6 * 18 = 8 * 18 = 144.

Use division before multiplication when calculating the LCM. The expression 48 / 6 * 18 reaches the same result as 48 * 18 / 6, but its intermediate value is 8 before the multiplication instead of 864. Smaller intermediate values reduce the chance of integer overflow when the inputs are larger.

The loop stops when the second value becomes zero

The algorithm needs two working values, often called a and b. While b is not zero, store the remainder of a divided by b, move b into a, and move the stored remainder into b. Storing the remainder first matters because assigning b to a changes the old value of a, and the next assignment still needs the old remainder calculation.

int originalA = 48;
int originalB = 18;
int a = originalA;
int b = originalB;

while (b != 0) {
    int remainder = a % b;
    a = b;
    b = remainder;
}

int gcd = a;
int lcm = originalA / gcd * originalB;

For 48 and 18, the loop visits (48, 18), (18, 12), (12, 6), and then (6, 0). At that point, a is 6, so the GCD is 6. The original values are still 48 and 18, which lets the LCM calculation use 48 / 6 * 18 and produce 144.