Let be an integer. A natural number is called a divisor of if there exists such that We write , say divides . We denote the set of all divisors by We write for the number of divisors of .

A natural number is called pime if it has exactly two divisors. Hence .

Let be integers. If and are not both , then the set of common divisors is finite and nonempty. We then define the greatest common divisor as and denote it by .

For every where there exists a unique pair of numbers and such that and .

Proof. The set is not empty, thus contains a minimal element . This gives us existence. Now to uniqueness: Let there be two pairs that fullfill our requirements. We now have . This gives us , but , which is only possible with . This forces as well.

The euclidean algorithm starts with two integers and and performs successive division with remainder until it is zero, like follows.

The algorithm computes the the greatest common divisor of and . For a proof see the Euclid's Theorem.

Two natural numbers are called coprime if their greatest common divisor is 1.

The euclidean algorithm computes the greatest common divisor.

Proof. TODO

For any natural numbers . There exist integers such that the gcd of can we written as .

Proof. Do the Euclidean Algorithm in reverse.

Let with the gcd of and equal to 1, and . Then .

Proof. From Bezout's Lemma there exists integers with . Multiply by to get . Since and by hypothesis, it follows that .