Proposition: 7.02: Greatest Common Divisor of Two Numbers - Euclidean Algorithm
(Proposition 2 from Book 7 of Euclid's “Elements”)
To find the greatest common measure of two given numbers (which are) not prime to one another.
- Let $AB$ and $CD$ be the two given numbers (which are) not prime to one another.
- So it is required to find the greatest common measure of $AB$ and $CD$.
Modern Formulation
See greatest common divisor.
Notes
- Euclid does not provide a definition of the greatest common divisor, he only provides a method to calculate it.
- Nowadays, it is not necessary to require that the numbers are not prime to one another to be able to find their greatest common divisor. There exists also a correct and efficient algorithm for finding the \(\gcd\) of any two integers, at least one of which does not equal \(0\).
- The contemporary definition of the greatest common divisor not given in Euclid's Elements has the advantage that \(gcd(0,0)\) is well-defined: \(0\) is the only integer, which is divisible by all other integers. Therefore, \(\gcd(0,0)=0\).
Table of Contents
Proofs: 1 Corollaries: 1
Mentioned in:
Proofs: 1 2
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
- non-Github:
- @Fitzpatrick
References
Adapted from (subject to copyright, with kind permission)
- Fitzpatrick, Richard: Euclid's "Elements of Geometry"
