Preparation

Watch the demonstration video on test-driven development¹ to learn how to work with doctests. This will make you understand the last two statements of the source code skeleton provided with this exercise.

Assignment

We provide you with a skeleton for the solution of this exercise. Your task is to implement the functions gcd and lcm, such that they respectively print the greatest common divisor and the least common multiple of two given integers $$a$$ and $$b$$. The greatest common divisor is the largest integer that is both a divisor of $$a$$ and $$b$$. The least common multiple is the smallest integer that is both a multiple of $$a$$ and $$b$$.

def gcd(a, b):
    
    """
    Computes the greatest common divisor of the two
    integers a and b.
    
    >>> gcd(252, 105)
    21
    >>> gcd(48, 18)
    6
    """
    
    # compute greatest common divisor based on the
    # Euclidean algorithm

def lcm(a, b):
    
    """
    Computes the least common multiple of the two
    integers a and b.

    >>> lcm(252, 105)
    1260
    >>> lcm(48, 18)
    144
    """
    
    # compute least common multiple

if __name__ == '__main__':
    import doctest
    doctest.testmod()

The fractions module from the Python Standard Library² already contains a function gcd that prints the greatest common divisor of two integers. However, for this exercise you cannot use the fractions module, as you come up with your own implementation of computing the greatest common divisor by yourself. The implementation of the gcd function should be based on the Euclidean algorithm. The algorithm starts with a pair of integers and computes a new pair that contains the smallest of the two integers and the difference of the largest and the smallest integer. This procedure is repeated until both integers have the same value. This value is the greatest common divisor of the original pair of integers.

The basic principle that is applied in the Euclidean algorithm, is that the largest common divisor does not change when the smallest integer is subtracted from the largest integer. As such, the greatest common divisor of 252 and 105 is also the greatest common divisor of 147 (= 252 - 105) and 105. As the largest integer is always lowered during each step of, the algorithm will ultimately stop when both integers are the same (if the procedure would be repeated yet another time, one of the two integers would become equal to zero).

The least common multiple of two integers $$a$$ and $$b$$ can be determined as the product of both integers, divided by their greatest common divisor.

Example

>>> gcd(252, 105)
21
>>> gcd(48, 18)
6

>>> lcm(252, 105)
1260
>>> lcm(48, 18)
144