Euclid (Did Euclid Need the Euclidean Algorithm to Prove Unique Factorization?)

 Author(s): David Pengelley and Fred Richman Source: The American Mathematical Monthly, Vol. 113, No. 3 (Mar., 2006), pp. 196-205 Published by: Taylor & Francis, Ltd. on behalf of the Mathematical Association of America Stable URL: Accessed: 07-10-2018 22:52 UTC JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at Mathematical Association of America, Taylor & Francis, Ltd. are collaborating with JSTOR to digitize, preserve and extend access to The American Mathematical Monthly This content downloaded from on Sun, 07 Oct 2018 22:52:09 UTC All use subject to Did Euclid Need the Euclidean Algorithm to Prove Unique Factorization? David Pengelley and Fred Richman 1. INTRODUCTION. The fundamental theorem of arithmetic says that every natu ral number is uniquely a product of primes. The heart of this uniqueness is found in Book VII of Euclid’s Elements [3]: Proposition 30 (Euclid’s Lemma). If a prime divides a product, then it divides one of the factors. Euclid begins Book VII by introducing the Euclidean algorithm. From his proof that the Euclidean algorithm works, he deduces an algebraic result: Porism (Algebraic Gcd Property). If a number divides two numbers, then it divides their greatest common divisor. 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 mag nitudes (“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 propor tionality 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. 2. THE EUCLIDEAN ALGORITHM. Euclid’s number theory is contained in Books VII through IX of the Elements. At the beginning of Book VII, he presents the Euclidean algorithm. The input to the algorithm is a pair of (positive whole) numbers a and b with a < b, and the algorithm consists of indefinite repetition of three steps: Repeat 1. if a divides b, return a; 2. while a < b, let b = b ? a; 3. let (a, b) = (b, a). Step 2 is the division algorithm: we keep subtracting a from b until b is less than a. Alternatively, we write b = qa + r, where r < a, and then replace b with r. In step 3 we interchange the roles of a and b, because b is now the smaller of the two. The Euclidean algorithm is supposed to return the greatest common divisor of a and b. To ensure that it does requires a proof, which Euclid supplies. His proof is essentially the first part of the following theorem, which we leave to the reader to verify.

15% off for this assignment.

Our Prices Start at $11.99. As Our First Client, Use Coupon Code GET15 to claim 15% Discount This Month!!

Why US?

100% Confidentiality

Information about customers is confidential and never disclosed to third parties.

Timely Delivery

No missed deadlines – 97% of assignments are completed in time.

Original Writing

We complete all papers from scratch. You can get a plagiarism report.

Money Back

If you are convinced that our writer has not followed your requirements, feel free to ask for a refund.

Open chat
Hello. Welcome to Quality Academic Help. How can we help you?