Quote: Euclid's algorithm for greatest common divisor; with proof

Quotation

Proposition 2 Given two numbers not prime to one another, to find their greatest common measure. Let AB, CD be the two given numbers not prime to one another. ... If now CD measures AB--and it also measures itself--CD is a common measure of CD, AB. ... But, if CD does not measure AB, then, the less of the numbers AB,CD being continually subtracted from the greater, some number will be left which will measure the one before it. [p. 129] For an unit will not be left; otherwise AB, CD will be prime to one another ... Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE. Since then, CF measures AE, and AE measures DF, therefore CF will also measure DF ... therefore CF measures AB, CD. ... I say next that it is also the greatest. ... PORISM. From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure. Q.E.D.   Google-1   Google-2

Published before 1923

Related Topics

Topic: mathematical proof (23 items)
Topic: constructing proof and program together (22 items)
Topic: kinds of numbers (24 items)