The greatest common divisor and the common multiple

exercise No. 110

Finding the greatest common divisor of two integer values Create comment in forum


We recall the section called “A class representing fractions”. So far no one demanded cancelling fractions. Yet calling new Fraction(4,8) will create an instance internally being represented by 4 8 rather than by 1 2 .

Cancelling fractions requires implementing e.g. the Euclidean algorithm in order to find the greatest common divisor (GCD) of two non-zero integer values.

Read the above link and implement a class method getGcd(long, long) inside a class Math:

public static long getGcd(long a, long b) ❶ {
  // Following
  return ??; //TODO

With respect to fractions one or both parameters a and b ❶ may be zero or negative. So we do have several special cases to handle:

a == 0 and b == 0

Return 1.

a == 0 and b != 0

Return absolute value of b.

a != 0 and b != 0

Return the gcd of the absolute values of a and b

Based on getGcd(...) implement the least common multiple of two long values:


Follow the test driven approach: Provide dummy methods and write tests prior to implementation of getGcd().

public static long getCommonMultiple(long a, long b) {...}


Implementing getGcd(...):

public static long getGcd(long a, long b) {

  // Following
  if (a < b) { // Swap the values of a and b
    final long tmp = a;
    a = b;
    b = tmp;
  while (0 != b) {
    final long r = a % b;
    a = b;
    b = r;
  return a;

Knowing the the gcd of two values a and b the common multiple may be obtained by a gcd b gcd gcd = a b gcd . Thus we have:

public static long getLeastCommonMultiple(long a, long b) {
  final long gcd = getGcd(a, b);
  if (1 == gcd) {
    return a * b;
  } else {
    return (a / gcd) * b;