 Welcome guest
You're not logged in.
290 users online, thereof 0 logged in

## Proposition: Greatest Common Divisor

Let $$a,b$$ be integers and let $$D_{a,b}$$ be the set of all common divisors of $$a$$ and $$b$$:

$D_{a,b}:=\left\{d\in\mathbb Z : d\mid a\wedge d\mid b\right\}.$

$$D_{a,b}$$ has a unique maximum $\max(D_{a,b})$, called the greates common divisor of $$a$$ and $$b$$, denoted by

$\gcd(a,b):=\max(D_{a,b}).$

We have $\gcd(a,b)\mid a$ and $\gcd(a,b)\mid b.$ Moreover, any divisor $d$ dividing both, $d\mid a$ and $d\mid b$ also divides their greatest common divisor $d\mid \gcd(a,b).$ For this reason, since $d\mid 0$ for all integers $d\neq 0$, we set $$\gcd(0,0):=0$$.

### Note

The division with quotient can be used to efficiently calculate the $\gcd$ of given two integers $a,b.$ See a Python implementation of the greatest common divisor algorithm.

## 1.Proof: (related to "Greatest Common Divisor")

(none)

### Bibliography (further reading)

 Landau, Edmund: “Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

 Scheid Harald: “Zahlentheorie”, Spektrum Akademischer Verlag, 2003, 3. Auflage