A machine has two gears. One of which has 15 teeth, the other has 24. In places the gears interlock, they are marked with a red line. What is the smallest amount of rotations the smaller gear has to make in order to get the markings next to each other?

The rotation can be calculated by dividing the lowest common multiple of the number of teeth of both gears by the number of teeth of the smallest gear. This is easily seen if we write out for every gear how many teeth pass the point where the gears interlock in one rotation: 

first gear: 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, 210, 225, 240, 255, 270, 285, …
second gear: 24, 48, 72, 96, 120, 144, 168, 192, 216, 240, 264, 288, 312, 336, 360, 384, 408, 432, 456, …

When the smallest gear has made eight full rotations, a total of 120 teeth have past the point where both gears interlock. This is the same number of teeth that passes the point when the largest gear has made 5 full rotations. 

Preparation

Watch the video on test-driven development¹ to learn to work with doctests. In doing so you will understand the two last statements in the skeleton of the source code that is given in this assignment. 

Assignment

Below, we have already constructed the skeleton of the solution of this assignment. Your task is to implement the functions gcd, lcm and rotations, so that they calculate the following properties for two gears $$a$$ and $$b$$: i) the greatest common denominator of the number of teeth, ii) the lowest common multiple of the number of teeth and iii) the minimum amount of rotations of the first gear after which the gears are back in their starting positions. The greatest common denominator is of course the largest integer that is a divisor of both $$a$$ and $$b$$. The lowest common multiple is the lowest integer that is a multiple of both $$a$$ and $$b$$.

def gcd(a, b):
    
    """
    Computes the greatest common divisor of the two integers a and b.

    >>> gcd(15, 24)
    3
    >>> gcd(252, 105)
    21
    """
    
    # calculation of greatest common divisor based on Euclid's algorithm

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

    >>> lcm(15, 24)
    120
    >>> lcm(252, 105)
    1260
    """
    
    # calculation of least common multiple

def rotations(a, b):
    
    """
    Computes the smallest number of rotations of a gear having a teeth that 
    puts gears with a and b teeth back into their initial position.

    >>> rotations(15, 24)
    8
    >>> rotations(252, 105)
    5
    """
    
    # calculation of number of rotations

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

The fractions module from the Python Standard Library² contains a function gcd that prints the greatest common denominator of two integers. However, it is prohibited to use the fractions module, you are supposed to calculate the greatest common denominator yourself. Base your implementation of the function gcd on the Euclidean algorithm. The algorithm starts with a couple of integers and uses them to form a new pair that consists of the smallest of both numbers and the subtraction of the largest and the smallest number. This procedure repeats itself until the pair consists of two equal numbers. That number is the greatest common denominator of the original pair of numbers. 

The basic principle that is used for this, is that the greatest common denominator doesn't change if the smallest number is subtracted of the largest number. Therefore, the greatest common denominator of 252 and 105 is also the greatest common denominator of 147 (= 252 - 105) and 105. Seeing as the largest number decreases, the repetition of this procedure results in smaller and smaller numbers, so that the repetition will stop sooner or later when both numbers are equal (if the procedure would be repeated once more after that, one of both numbers would become 0).

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

Example

>>> gcd(15, 24)
3
>>> gcd(252, 105)
21

>>> lcm(15, 24)
120
>>> lcm(252, 105)
1260

>>> rotations(15, 24)
8
>>> rotations(252, 105)
5