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\).
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.
Proofs: 1
Algorithms: 1 2
Corollaries: 3
Definitions: 4 5
Lemmas: 6
Motivations: 7
Proofs: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Propositions: 25 26 27 28 29 30 31 32 33 34
Theorems: 35
