### The greatest common divisor and the common multiple

No. 109

#### Finding the greatest common divisor of two integer values

Q:

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 http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html
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:

### Tip

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

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

A:

Implementing getGcd(...):

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

// Following http://www.math.rutgers.edu/~greenfie/gs2004/euclid.html
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;
}
}