Did Euclid need the Euclidean algorithm to prove unique factorization?

Euclid’s lemma can be derived from the algebraic gcd property, but it is not at all apparent that Euclid himself does this. We would be quite surprised if he didn’t use this property because he points it out early on and because we expect him to make use of the Euclidean algorithm in some significant way. In this paper, we explore the question of just how the algebraic gcd property enters into Euclid’s proof, if indeed it does. Central to Euclid’s development is the idea of four numbers being proportional: a is to b as c is to d. Euclid gives two different definitions of proportionality, one in Book VII for numbers (“Pythagorean proportionality”) and one in Book V for general magnitudes (“Eudoxean proportionality”). We will discover that it is essential to keep in mind the difference between these two definitions and that many authorities, possibly including Euclid himself, have fallen into the trap of believing that Eudoxean proportionality for numbers is easily seen to be the same as Pythagorean proportionality. Finally, we will suggest a way to make Euclid’s proof good after 2300 years.