Calculate the greatest common divisor of 15 and 70.

## - Prime numbers and the Sieve of Eratosthenes - Group A only -

Some integers in particular play a role of primary importance: these are the integers whose GCD is 1.

Definition 2.2.11.

Let $a$ and $b$ be two integers. We say that $a$ and $b$ are coprime if $a \wedge b=1$.

For example, 2 and 3 are coprime, whereas 4 and 6 are not, since they are both even.
It is enough to apply Euclid's algorithm: it is easily verified that $70=15 \times 4+10$, then
that $15=10 \times 1+5$, and finally that $10=5 \times 2+0$. This shows that $70 \wedge 15=5$, which was not really surprising anyway.