This function implements Euclid's algorithm for finding
the greatest common divisor of two numbers

and `a`

.
`b`

rational.py

def gcd ( a, b ): '''Greatest common divisor function; Euclid's algorithm. [ a and b are integers -> return the greatest common divisor of a and b ] '''

Euclid's algorithm is easily defined as a recursive
function. See *Structure and Interpretation
of Computer Programs* by Abelson and Sussman,
ISBN 0-262-01153-0, pp. 48-49.

The GCD of any number

and zero is zero.`x`

The GCD of any two nonzero numbers

and`a`

is the same as`b`

`GCD(`

.,`b`

modulo`a`

)`b`

Defined recursively, this amounts to:

rational.py

if b == 0: return a else: return gcd(b, a%b)