Coprime numbers

The integers a and b are said to be coprime or relatively prime if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1.

For example, 6 and 35 are coprime, but 6 and 27 are not because they are both divisible by 3. The number 1 is coprime to every integer; 0 is coprime only to 1 and −1.

A fast way to determine whether two numbers are coprime is given by the Euclidean algorithm

Euclidean algorithm:

Given two natural numbers a and b: check if b is zero; if yes, a is the gcd. If not, repeat the process using (respectively) b, and the remainder after dividing a by b. The algorithm can be naturally expressed using recursion:

function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)

or using iteration (more efficient with compilers that don't optimize tail recursion):

function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a