Testwiki:Featured article candidates/Euclidean algorithm/archive1

The following is an archived discussion of a featured article nomination. Please do not modify it. Subsequent comments should be made on the article's talk page or in Wikipedia talk:Featured article candidates. No further edits should be made to this page.

The article was promoted by Karanacs 21:05, 19 May 2009 [1].

---

Euclidean algorithm

Nominator(s): Proteins (talk) 16:22, 27 April 2009 (UTC)

{{Wikipedia:Featured article tools|1=Euclidean algorithm}}

I am nominating this mathematical article because I believe it meets the Featured Article criteria. In its simplest form, the Euclidean algorithm is often taught to 10-year-old children; for many, it is the only algorithm they encounter in school. It has several important applications, such as the RSA algorithm (often used in electronic commerce) and solving Diophantine equations. Although the oldest known algorithm (23 centuries), it continues to play a role in developing new mathematics. It would be helpful for Wikipedia to have an excellent article on this topic, both for itself and for the introduction it provides to advanced mathematics such as abstract algebra. Proteins (talk) 16:22, 27 April 2009 (UTC)

Game of Euclid

I'm a bit concerned about the inclusion of the "Game of Euclid" in the historical development section. It doesn't seem to be very important as a research topic or achievement, and it certainly doesn't even come close to the other developments in that section. What was the reason for including this? --C S (talk) 17:19, 27 April 2009 (UTC)

The FA criteria require that the article be "comprehensive" (criterion 1b). I admit that the game of Euclid is relatively unimportant, but it has been discussed in mathematical journals and textbooks, as referenced in the article. There didn't seem to be a better place to put that material besides "Historical development". Proteins (talk) 17:43, 27 April 2009 (UTC)

Well, I spy less than half a dozen "mathematical journals and textbooks" that mention the game. Surely there are many topics with more coverage that have not been included in this article. So I can't see how omitting this game would violate criterion 1b. Not to mention, these math journals you talk of are mainly math education related ones, except the journal INTEGERS, which seems like an ok journal but not particularly well-known. Of course, I don't mean to disparage journals whose primary audience may be math educators, but in terms of using such journals as a justification for including a mathematical topic in this article, I don't think it is sufficient. One has to separate a topic which is primarily used as an educational device from a topic which is considered an important development in understanding of the Euclidean algorithm. --C S (talk) 19:23, 27 April 2009 (UTC)

Oldest algorithm?

I think that the sentence "The Euclidean algorithm is the oldest algorithm in the historical record" is wrong because of Old Babylonian algorithms used to solve problems. --El Caro (talk) 18:04, 27 April 2009 (UTC)

This is a good point. The passage stated is uncited, but there is further down a box with a quote by Knuth which makes the nuanced observation that it is the "oldest nontrivial algorithm" that has survived to the present day. Since Knuth actually wrote an article in 1972 on ancient Babylonian algorithms [2] where he examined written records of their algorithms, presumably he was aware that the "nontrivial" is an important and necessary modifier. "Oldest nontrivial...", of course, is his opinion. --C S (talk) 19:21, 27 April 2009 (UTC)

I've read the quote in the box. Is this "only" Knuth's opinion or a statement on whom most specialists agree ? --El Caro (talk) 19:39, 27 April 2009 (UTC)

If "algorithm" is defined only as a set of numerical rules (without requiring proof that the rules always work or understanding why they work), then surely there were algorithms for thousands of years before Euclid. I'll review the literature and list the opinions of other people besides Knuth. Proteins (talk) 20:25, 27 April 2009 (UTC)

I corrected this in the text before, but that is indeed what "algorithm" means. I have never seen anyone define algorithm to mean it must come with understanding of the person using it or a proof that it works. So I can't imagine Knuth would use some nonstandard definition of "algorithm", as you suggest, especially since he is a computer scientist and certainly computer scientists do not require algorithms come with proofs. That is probably why he says "nontrivial" as I mentioned above. --C S (talk) 20:40, 27 April 2009 (UTC)

After consulting more than a dozen mathematical sources, I concede that you are entirely correct. An algorithm is any well-defined (alpha)numerical procedure, and can well be incorrect. Thus, pre-Pythagorean carpenters constructing a right angle by a 3-4-5 triangle were using an algorithm, and so were carpenters who used a 2-3-4 triangle. I accepted the proof requirement (which I read elsewhere) because Knuth's argument for the EA's priority seemed incompatible with the obvious prior existence of many algorithms, such as calendars, money changing, tax and inheritance systems, measurement of area, architecture, multiplication and division, etc. I have also not found a reliable source besides Knuth that identifies an oldest nontrivial algorithm. The solution for this FAC may well be to leave the quote box from Knuth, but to change the assertion in the article. How about "oldest numerical algorithm still in common use", or "one of the oldest algorithms in the historical record"? Would either of those wordings be acceptable? Proteins (talk) 02:45, 29 April 2009 (UTC)

Hi Proteins. Well, as you said, multiplication algorithm was around before, so I'm unhappy with the first phrasing. The second seems acceptable. Actually, I had a bit of fun digging around the Google searches for "euclidean algorithm oldest". I had no idea that there was such a common misconception of the Euclidean algorithm being the oldest algorithm (with no qualification). Perhaps Wikipedia itself has had a role in perpetuating this. In "Mathematica in Action" by Stan Wagon [3], Wagon asserts "The Euclidean algorithm for computing the gcd of two numbers is arguably the best algorithm in all of mathematics. According to Knuth, it is the oldest nontrivial algorithm that has survived to the present day." So here Knuth's assertion of "oldest nontrivial..." is repeated with the addition that it is the best algorithm bar none. However, misleadingly, the section heading proceeding the passage states "The oldest surviving algorithm"! In this book, the author asserts, the "Most likely, it is the oldest mathematical algorithm in existence". Oops! Anyway, although the Wagon claim is on the strong side, I think the Knuth quote really has some content there. So I think we ought to keep that in the box, while in the text we can make a more unobjectionable assertion like "one of the oldest...record". --C S (talk) 06:56, 29 April 2009 (UTC)

Applied to real numbers

"Euclid's algorithm can be applied to real numbers, as described by Euclid in Book 10 of his Elements" looks like an anachronism. Did Euclid know real numbers ? --El Caro (talk) 18:17, 27 April 2009 (UTC)

Well, now we're getting into metaphysical matters that I think are tangential. For example, when Euclid considered arithmetical operations on whole numbers, it's not the same in a sense as what we consider such arithmetic, nor is probably what the ancient Greeks considered whole numbers the same as what we do now. So strictly speaking Euclid did not know real numbers, but he didn't know whole numbers, addition, or subtraction either. So that makes your point kind of moot. --C S (talk) 19:21, 27 April 2009 (UTC)

The ancient Greek certainly knew about irrational numbers, at least as surds, even if they hadn't defined Dedekind cuts. Book X of Euclid's Elements is devoted entirely to questions of incommensurability, and this real-number version of Euclid's algorithm begins that exposition. Knuth states elsewhere that the Greeks treated real numbers by infinite continued fractions, but he doesn't explain his remark further; I took him to be referring to this version of Euclid's algorithm. One could argue, I suppose, that the modern concept of real numbers embraces more than just "the set of all rational and irrational numbers", but that seems beyond the level of this article. Proteins (talk) 20:18, 27 April 2009 (UTC)

Ancient Greeks considered numerical concepts mainly in terms of geometric constructions ala ruler and compass and that is how Euclid's treatment of commensurability goes. This is certainly not the way modern mathematicians think of them. Sure the ancient Greeks knew of some irrational numbers, but they certainly didn't know "e" or many other irrational numbers that are not constructible. So their concept of irrational number was far more limited than our modern understanding, even when one limits the concept of real number to mean "set of rational and irrational numbers". Even on the math where modern and ancient understanding would seem to overlap, it's clear the ancient Greeks just had a different way of thinking about it, so in a metaphysical sense, you could argue that the objects are really different. --C S (talk) 20:40, 27 April 2009 (UTC)

Oppose on criterion 3

• File:Gabriel-Lamé.jpeg - There is no source, date, or author for this image that would lead us to believe that it is in the PD. We need to be able to verify that it is in the PD. More research on this image needs to be done.
• File:Dedekind.jpeg - The website for this image does not indicate the 1870 date and we have no name or death date for the photographer, so we cannot verify the PD license listed. More research on this image needs to be done.

These issues should relatively easy to resolve. I look forward to reading the entire article. Awadewit (talk) 21:13, 27 April 2009 (UTC)

Unfortunately, despite a diligent search, I have not been able to verify the copyright status of either image. Both were taken around 1870 (roughly 140 years ago) and both are widely distributed on the Internet. However, it is conceivable that the original photographer died less than 70 years ago, or that the photographs themselves were not published until more recently. I found a similar image of Lamé published in 1897, but the Ecole polytechnique asserts its unrestricted copyrights. I found an alternative photograph of Dedekind published in 1930 in Braunschweig as part of his Collected Works; however, I cannot verify that it is out of copyright, either. I'll remove the images for now, pending a fuller investigation. They're not essential. Proteins (talk) 02:45, 29 April 2009 (UTC)

Ah, good news! We can use the Lame picture from 1897 then. It doesn't matter if Ecole Polytechnique claims copyright; US copyright law is what Wikipedia requires us to follow and that means the picture is considered in the public domain in the US (see Wikipedia:Public_domain). --C S (talk) 04:42, 29 April 2009 (UTC)

We can use the the French Lamé. As CS explains, it is acceptable under US copyright law. You can upload it to the English Wikipedia. Awadewit (talk) 01:11, 30 April 2009 (UTC)

Lack of citations?

• Problem - many of the paragraphs are lacking citations or, if having them, there are no citations covering many sentences. See the end of the section "Greatest common divisor" for just one example. This needs to be fixed before it can pass FAC. Ottava Rima (talk) 23:45, 27 April 2009 (UTC)

• • If you are referring to the subsection that begins, "Three related mathematical methods are used often in the arguments below..." That is an explanatory paragraph explaining the article elements, in particular, explaining what typical math proof method will be used further down. That does not require citation. Looking through the article, I see plentiful citations. I suspect what Ottava Rima is referring is to paragraphs where the initial statement might be sourced, but further explanation or example is not (although it is simply a further explication of what the initial sentence said). I wonder if Ottava Rima is familiar with WP:SCG, since I cannot see how the article fails the SCG. I think there is some confusion that would be remedied by reading "Examples, derivations and restatements" section of the SCG in particular. --C S (talk) 23:58, 27 April 2009 (UTC)
    • Unless it is sourced, it is possibly Original Research. Now, from the guideline that you quoted: "The no original research and verifiability policies are of paramount importance to Wikipedia. Information presented in Wikipedia should be easily verifiable by anyone who wishes to do so. To ease verification, sources should be detailed by the articles." This article fails that. The whole page has over 50 sections needing citations. Such things are 100% unacceptable in an FA. Ottava Rima (talk) 00:26, 28 April 2009 (UTC)
      • You've been claiming a lot citation violations, but have yet to demonstrate one example. Could you show me an example paragraph from the article that violates the SCG? You cited the opening sentences of the SCG, but I'm not sure you've read further past it since the rest of the introduction explains that there are different ways to satisfy these core polices. Then further on down in the first section it is explained that not every sentence or paragraph may require a citation depending on the type of material. --C S (talk) 01:27, 28 April 2009 (UTC)
        • Violations? No. FA has as a requirement that everything is verifiable. This requires all information to be cited. There are over 50 spots that need citations. I read through the whole article, as, when working on my classics degree, Euclid books 1, 2, 3, 5, and 6 were included, so a page dealing with Euclid is something that I find interesting. Ottava Rima (talk) 03:08, 28 April 2009 (UTC)
          • Yes it's true that FA has a verifiability criterion. But it does not automatically follow that all information is needed to be cited. This is a logical jump not supported by any listed policy, guideline, or FA criterion. In addition, SCG has been found to be satisfactory in prior FA nominations by Raul and Sandy. So I'm afraid your opinion is just your opinion, without consensus, and will probably be ignored as far as this nomination goes. --C S (talk) 03:51, 28 April 2009 (UTC)
          • I agree with CS. Please re-read Wikipedia:Verifiability to gain a better understanding of the policy. My only quibble with respect to verifiability was the "oldest algorithm" bit. The discussion above has laid that objection to rest. Lwnf360 (talk) 06:10, 28 April 2009 (UTC)
            • Sorry, you two, but I've been here for a long time, I've worked on many FACs, FARs, and the rest. I know what the verifiability criterion is. Your arguments have shown that this wont be corrected, so I have no choice but to oppose. 13:20, 28 April 2009 (UTC)

As a conciliatory gesture to a numerically-minded classicist, I'll be glad to add some more references to the 130 already there. When I've finished, please reconsider your strong oppose. Proteins (talk) 02:45, 29 April 2009 (UTC)

I've added 22 more references. Proteins (talk) 17:20, 30 April 2009 (UTC)

There are just a few more passages that I think need to be cited: 1) "However, the solutions cannot shrink indefinitely, since...." until the end. 2) "The remainder is equivalent to the congruence class in modular arithmetic." 3) "A generalization of this result is known as Sturm's theorem." 4) "Bézout's identity, and therefore the previous algorithm, can both be generalized to the context of Euclidean domains." 5) "The GCD is said to be the generator of the ideal of a and b. This GCD definition led to the modern abstract algebraic concepts of a principal ideal..." 6) "this is impossible for a system of linear equations when the solutions can be any real number." 7) "Such finite fields can be defined for any prime p; using more sophisticated definitions, they can also be defined for any power m of a prime pm. Finite fields are often called Galois fields, and are abbreviated as GF(p) or GF(pm)." 8) "Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. For comparison, the efficiency of alternatives to Euclid's algorithm may be determined." (statement of practice definitely needs a citation for verification) 9) "In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization..." (see above about statements of practice) 10) "The polynomial Euclidean algorithm has other applications as well, such as Sturm chains...." 11) "Many of the other applications of the Euclidean algorithm carry over to Gaussian integers." 12) "This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later, Richard Dedekind to ideals." 13) "An important generalization of the Euclidean algorithm" (characterization as "important").

Question - do you cite a first line, but that citation carries into the next? That could be a problem, because your citations would cover the next sentences but you don't place them where they would acknowledge that. Ottava Rima (talk) 14:54, 8 May 2009 (UTC)

Comment on terminology

Often in math books, the Euclidean algorithm is not the actual procedure for finding the GCD, but rather the statement that for two a, b (natural numbers, integers, residue classes of integers, polynomials over commutative rings, power series over complete local rings, and so forth) we can solve the equation: $a=bq+r$ uniquely with a (degree) condition on r (and some conditions on a and b). They are related, of course, but I was wondering if it might be worthwhile saying something to that effect off the bat. Fowler&fowler«Talk» 17:43, 28 April 2009 (UTC)

Perhaps you're referring to the "division lemma" or division algorithm? If so, the article mentions it in the subsection "Calculating the quotients and remainders". But I haven't encountered a source that calls it the "Euclidean algorithm"; could you point me towards one? Proteins (talk) 02:45, 29 April 2009 (UTC)

I had a vague feeling Fowler had a point there, so I dug through some books I had handy. I found that (as expected) Hardy & Wright's number theory book states that "Euclid's algorithm" is defined by generating the sequence of remainders which terminates (it seems to give no name for the "division algorithm", merely calling it division with remainder at times), Dummit & Foote's abstract algebra book states that the "Euclidean algorithm" comes from the division algorithm, but Herstein's Topics in Algebra does indeed call the above, the Euclidean algorithm. Herstein is a pretty well-known algebra book, so I dug a bit more and I found that a source on the Euclidean domain article, which was published in the Bulletin of the American Mathematical Society in 1949, also uses the term Euclidean algorithm for division algorithm (see [4]). I think in number theory books there is a pretty well-established tradition of using "Euclidean algorithm" to mean generating the sequence of remainders from the two initial numbers. In algebra texts that discuss Euclidean domains, my suspicion is that books here and there may use Euclidean algorithm to mean division algorithm but I suspect that modern books generally don't; I find Dummit & Foote is pretty reliable regarding modern terminology, while Herstein is from 1961 and sometimes a bit outdates on terminology. In any case, I think a note or footnote is in order. --C S (talk) 04:59, 29 April 2009 (UTC)

Yes, I guess you are right: number theory texts do call it the "division algorithm," and in fact, come to think of it, in high-school we called it the "division algorithm" ourselves, perhaps because it was introduced as a part of elementary number theory. Somewhere in college though the name became less certain (as I remember it). As for texts, among the classic algebra texts, both van der Waerden and Birkoff/Mac Lane do call it the "division algorithm," but Herstein doesn't (as you say). The more recent texts seem to be a mixed bag. I don't know Dummit and Foote, but among the books published in the last 20 years that refer to the "division algorithm" as the "Euclidean algorithm" are (the links should take you straight to the page about the "Euclidean Algorithm"): Hilton and Wu's A Course in Modern Algebra (1989), Rowen's Algebra: Groups, Rings, and Fields (1994), Lang's Algebra: A Graduate Course (2002), Murty and Esmonde's Problems in algebraic number theory (2004), Lang's Undergraduate Algebra (2005), and Lowen's Graduate Algebra: The Noncommutative View (2008). Lang (2002), in particular, is still widely used, I think. So the footnote will be useful for any others who have questions like mine.  :) Thanks! Fowler&fowler«Talk» 12:26, 29 April 2009 (UTC)

I didn't check all those books publication dates, but certainly Lang's well-known classic Algebra is not really a book "published in the last 20 years". The revised 3rd edition is from 2002, but the original was from 1965, and subsequent versions are essentially the same (but with fixing of errors and so forth). Unlike the others you mention, which I've never heard of, certainly it is still used (mainly by the top graduate programs and more that like to think they are in the same class). --C S (talk) 20:47, 29 April 2009 (UTC)

Actually I expect the Hilton and Wu book must be from the 60s too, since "Hilton" is Peter Hilton and he wrote several books in that period, all of which are well regarded but never really caught on like their competitors. Indeed, Hilton is rather infamous (in a humorous way) for writing a book on homology/cohomology (with Wylie) and using the terms homology and cohomology to refer the opposite way as everyone else used them. That never changed in subsequent editions even though by then it became clear they had lost the terminology reformation attempt. Herstein is also a bit weird in that he composes linear transformations from left to right instead of right to left. That never changed in recent printings. So anyway, if your point (which I think it may be) is that even though these books are old, but they were recently republished and so must reflect more modern terminology, I'm afraid I don't buy that. In my experience, republished classic texts often retain their classic (read: outdated) terminology, and the reader is supposed to be on guard for it. --C S (talk) 21:01, 29 April 2009 (UTC)

My point was simply that these books, regardless of their provenance, are still being used by students (as both books by Lang are, by your own admission), so it doesn't hurt to have the note. I have no idea if the terminology is outdated. Certainly Lowen's Graduate Algebra: The Noncommutative View (2008), published by the AMS does look recent. Anyway, this is not a biggie for me. Regards, Fowler&fowler«Talk» 22:23, 29 April 2009 (UTC)

I understand and agree wholeheartedly. Perhaps I should have forestalled your comments by mentioning that Herstein is still a widely used book. --C S (talk) 23:02, 29 April 2009 (UTC)

I have added the following as a footnote to the introductory sentence: Some widely-used textbooks, such as I. N. Herstein's Topics in Algebra and Serge Lang's Algebra, use "Euclidean algorithm" to refer to division algorithm.

I don't know if that's the best place for it, but it should save some confusion on terminology. --C S (talk) 23:09, 29 April 2009 (UTC)

Comment on animation in lead

• I oppose anything that flashes. Sorry, I know it's cool but it's very distracting to readers. Looie496 (talk) 16:20, 29 April 2009 (UTC)

I've found a way to hide the animation until it's requested. Proteins (talk) 17:20, 30 April 2009 (UTC)

Intelligibility

It's excellent that the atmosphere here is cordial and constructive; I appreciate everyone pitching in to make the article better. For my part, I'm determined to make the article as intelligible as possible to lay-readers. I'd appreciate advice on how to do that, or alerts to obscure sections. Thanks! (We should continue this discussion on the article talk page.) Proteins (talk) 17:20, 30 April 2009 (UTC)

• The article should NOT have its technical aspects toned down. Readers searching for information on the topic will 9 times out of 10 be looking for the technical explanation. The technical explanations are excellent. Lwnf360 (talk) 23:08, 30 April 2009 (UTC)

Thank you, and no worries! I just want to avoid unnecessary obscurity. Proteins (talk) 00:01, 1 May 2009 (UTC)

!Votes

• Conditional Support. Overall, the article is excellent and it certainly meets criteria 1 and 2. In fact, arguments could be made that the article is too comprehensive i.e. includes too much on related topics (criterion 4). However, I would not support that argument. The image copyright issues raised by Awadewit should be corrected. Unless I have missed something major, in my view, the article should be featured. Lwnf360 (talk) 06:10, 28 April 2009 (UTC)

Thank you, and I hope that the copyright issues will now be resolved. Proteins (talk) 02:45, 29 April 2009 (UTC)

• Strong Oppose - lack of citations for over 50% of the page means that it fails the citation requirements. Ottava Rima (talk) 13:20, 28 April 2009 (UTC)

• Looking to support. I haven't read it yet, but it looks pretty good. Will make vote more definite upon reading. Fowler&fowler«Talk» 12:28, 29 April 2009 (UTC)

• Support. I have (inofficially) reviewed the article recently and found it very good (see the article talk page), and think it has even improved since. It is very comprehensive, accessible, provides pictures where useful. I only have one suggestion, which is easy to fix: please consider adding reference(s) for the section "Induction, recursion and infinite descent". I don't agree with Ottava Rima's point above, which is exaggerating verifiability, but that section could do with a brief reference for each of the three methods, just in the sense of a "further reading", if readers are interested in learning more about induction etc. (A reference mentioning these techniques in correlation to the EA would be ideal.) Jakob.scholbach (talk) 21:47, 29 April 2009 (UTC)
  • Yet, is that not why we have separate articles on mathematical induction, recursion and infinite descent? Each of which has a well-written, extensive introduction, and with the except of 'infinite descent' has plentiful references? Is your suggestion because you don't like the look of a paragraph without footnote symbols? I'm genuinely confused by your comment, as we don't have a reference in the article for many other terms either (like ideal (ring theory). I would suggest just adding some references to infinite descent instead. --C S (talk) 23:02, 29 April 2009 (UTC)
    • Oh, that was not my intention. It is not that I a priori don't like paragraphs without footnotes, I just think it is a service to the reader to come up with a reference. For example mathematical induction does give a number of references, which is good, but assume you don't have the time nor ability to read that article nor scan all the references given there. In that case, an additional reference (in this article here) would be helpful, wouldn't it? Secondly, it is reassuring to have good surrounding articles, but you can't be sure of what happens with them. (You are right, taking that idea seriously would also mean to add references for all other notions like ideals, but I think ideals are far less crucial to the EA than induction etc.) Jakob.scholbach (talk) 06:16, 30 April 2009 (UTC)
      • Regarding the first concern I suppose I have a hard time seeing how providing a reference footnote would be helpful. If I don't have time to read one of the linked articles, I don't see why I would have time to go look up some reference in the library or read some other website or read some downloaded paper. I can see the point of the second concern, that something bad can happen to a linked article. I suppose it doesn't hurt to copy over some of the references from those articles; I'd feel a bit too silly doing that myself, so I'll leave that to you :-). --C S (talk) 06:57, 30 April 2009 (UTC)
        • These are good suggestions! I've added some textbook references to the "Induction, recursion and infinite descent" section. Proteins (talk) 18:47, 30 April 2009 (UTC)

• Leaning to support. I haven't looked through the the whole article, but will do so. The "Game of Euclid" thing is not a good addition, but that can be argued (by those who care to) on the article talk page. Other issues discussed above all seem resolved. --C S (talk) 23:02, 29 April 2009 (UTC)

• Support the lead - I have a very hard time reading mathematics articles. I tried very hard to understand this, but I kept getting lost. I understood the lead, but after that, not much. I'm too verbal, I suppose. (Even the diagrams slightly confused me. I was like, "why are there 10 squares?") Anyway, the lead makes sense to idiots such as myself. Awadewit (talk) 01:18, 30 April 2009 (UTC)

• • Perhaps the 10 square example could be improved. It's not important the exact numbers that are being used there. The basic idea is that the gcd of two numbers is the largest length which can be used as a unit for both numbers. So for the two numbers illustrated by the 10 square picture, the gcd fits in one number twice and fits in the other number 5 times. This is illustrated by the 5 x 2 grid. There is no way to tile that rectangle with a bigger square. --C S (talk) 01:40, 30 April 2009 (UTC)

• • Ok, so I rewrote the passage with the visualization example to say:

    Imagine a rectangular area a by b. Suppose d divides both a and b with no remainder. So we can divide the sides of the rectangle into some number of segments of length d and furthermore divide the rectangle into a grid consisting of squares of side length d. The greatest common divisor g equals the largest value of d for which this is possible. For illustration, a 24×60 rectangular area can be divided into a grid of: 1×1 squares, 2×2 squares, 3×3 squares, 6×6 squares or 12×12 squares. Thus, 12 is the greatest common divisor of 24 and 60.

    Is this an improvement? --C S (talk) 07:11, 30 April 2009 (UTC)
    • I didn't follow the thread of edits, but talking to the reader ("imagine ...") and "we" should be avoided as unencyclopedic language. Jakob.scholbach (talk) 07:45, 30 April 2009 (UTC)
      • Proteins is responsible for the "imagine". :-) In any case, WP:MOSMATH is ok with limited usage of this type. If MOSMATH is inconsistent with FA, that's a shame. Feel free to edit my version. --C S (talk) 08:02, 30 April 2009 (UTC)
        • I don't think there is a problem with such language (particularly when explaining examples) - it is used by professional mathematicians. If it is good enough for them, it should be good enough for us. Awadewit (talk) 09:04, 30 April 2009 (UTC)

• Minor suggestion for improvement. The animated gif File:Euclidean algorithm 1071 462.gif is a very nice idea, especially for readers with limited math knowledge. But it would be more useful if the dimensions of the successive rectangles were given. (Hope you see what I mean) They're given in the caption but that forces the reader to look at the image, go to the caption, return to the image and pedagogically I think that's suboptimal. Also I think it's one of these rare cases where it makes sense to point out on the caption that clicking on the image will enlarge it (many readers are unaware of this). Pichpich (talk) 16:11, 1 May 2009 (UTC)

Those are both good suggestions, Pichpich, thank you. Although they may be more difficult to implement elegantly than you imagine, I'll work on them. Originally I left the numbers out of the animation on purpose, because I wanted it to be usable on other Wikipedias that do not use our digits, such as the Arabic Wikipedia. Proteins (talk) 10:25, 3 May 2009 (UTC)

• Support. I really like this article. It's comprehensive, well-written, interesting, and informative. I do have one minor quibble, although I'm not sure anything can be done about it, and it's that at least on my laptop screen some of the formulae are difficult to read. For instance, in

r_k−2 = q_k r_k−1 + r_k

q_k r_k−1 looks like q_k to the power of r_k−1. It may just be an artefact caused by the tail of the "q" though, either that or my tired old eyes. :-) If nobody else has a similar problem I'll just chalk it down to my default character set. --Malleus Fatuorum 13:57, 2 May 2009 (UTC)

Thank you! I sympathize with the small-equation issue, although the equations read correctly on my screen. The equations could've been rendered better in math mode (LaTeX), but that approach produces images that are not accessible to people using standard screen readers. Perhaps the best long-term solution for Wikipedia and other Wikimedia projects would be a script that generates ALT text automatically for a given math-mode equation, while allowing the editor to fine-tune its output. That would require a major investment of time and effort, however. Proteins (talk) 10:16, 3 May 2009 (UTC)

• Comments - sources look okay, links not checked with the link checker tool, as it was misbehaving. Ealdgyth - Talk 16:58, 3 May 2009 (UTC)

• Comments from Cryptic C62 · Talk
  • The lead does not adequately summarize all of the main sections of the article. Unless I am misreading, it appears that Other number systems is not represented in the lead.

    Apparently you missed the sentence "In the 19th century, the algorithm was generalized to other types of numbers, which led to modern abstract algebraic notions such as Euclidean domains." in the lead. But you're right, that's too terse, so I expanded it to "The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains." Proteins (talk) 09:59, 4 May 2009 (UTC)

  • Caption: "The greatest common divisor of a and b is the largest square tile that covers an a-by-b rectangle exactly. Here, a 24-by-60 rectangle is covered with 12-by-12 square tiles." In the first sentence, it needs to be made clear that it is not one single square tile that covers the rectangle, but multiple iterations of that square tile. "exactly" is somewhat ambiguous, consider expanding. It would also be helpful to say "ten 12-by-12 square tiles". Addendum: upon reading the relevant paragraph, it might be helpful to make this into an animation which demonstrates the various ways in which a 60-by-24 rectangle can be divided.

    Reworded caption, thanks. The animation might be helpful, but that would require someone to create and position precisely 1440 1-by-1 squares. It's possible — are you volunteering, by any chance? Proteins (talk) 09:59, 4 May 2009 (UTC)

    I'm not familiar with how to convert a series of images into an animation, but I'd be willing to make the images (or at least try). If I make them, can you make the animation? --Cryptic C62 · Talk 18:52, 4 May 2009 (UTC)

  • "The greatest common divisor is often written as GCD(a, b) or, more simply, as (a, b)." Yes, the second version is simpler, but that notation is also used for lots of other things in mathematics. What (a, b) represents depends on the context of the problem, and I think it would be wise to mention this so as not to mislead our less mathematically-inclined readers.

    Mentioned ambiguity of "(a, b)" notation, and swapped order of last two sentences in paragraph for better flow. Proteins (talk) 10:10, 5 May 2009 (UTC)

    Eh, better, but instead of "although the simpler notation is also used for unrelated mathematical objects, such as two-dimensional vectors." how about "although the latter notation is also used for various other mathematical concepts, such as two-dimensional vectors."

    That's a good suggestion! I followed your wording more-or-less exactly. Proteins (talk) 02:29, 6 May 2009 (UTC)

    I was hesitant to use the word "unrelated", but I couldn't figure out exactly why. Here's why: "unrelated" may imply that the two components, a and b, are unrelated, which is obviously never the case. "other" makes it clear that the concepts are unrelated to EA without introducing the ambiguity. --Cryptic C62 · Talk 00:57, 8 May 2009 (UTC)

    Just to clarify, the wording now is "although the latter notation is also used for other mathematical concepts, such as two-dimensional vectors." Proteins (talk) 15:52, 14 May 2009 (UTC)

  • "neither 6 = 2×3 nor 35 = 5×7 is a prime number, since they both have two prime factors" I think it may be a tad confusing to include the prime factorization at first; perhaps this should be added later: "neither 6 nor 35 is a prime number, since they both have two prime factors: 6 = 2x3 and 35 = 5x7." or something like that. Also, shouldn't it be "neither 6 nor 35 are prime numbers" ?

    Excellent suggestion for the rewording. Proteins (talk) 09:59, 4 May 2009 (UTC)

    Neither/nor - it depends if you think 6 and 35 are singular or plural. Are they singular because they are individual numerals or are they plural because they abstractly represent "more than one"? Tricky. Awadewit (talk) 20:05, 3 May 2009 (UTC)

    Hrm. Well, I'm not particularly sure about it myself, so use your best judgment. I just wanted to bring it to your attention. --Cryptic C62 · Talk 22:23, 3 May 2009 (UTC)

    In my way of thinking, it depends how we are using "6" in the context. Since we say "6 is composite" (just as we say "7 is prime"), it seems to me we are thinking of it as singular.

    "Neither," the converse of "both," usually has singular verb concord (as the Bartleby reference suggests as well). So, "Neither 6 nor 35 is prime" sounds correct to me. The adjective "prime" will not apply to instances of plural occurrences of 6; in other words, you can't apply "prime" to "six sheep," although you can say, "The number of sheep (viz. 6) is prime." That is as far as prescriptive grammar goes. If you look at usage on the web, "Neither * nor * is" has approximately 7 million hits, whereas "Neither * nor * are" has 16.4 million hits (some are using "are" for plurals, but not all). So, even though most prescriptive grammar books don't look kindly upon plural verb agreement for "neither" in the case of third person singular nouns, as in "Neither Hamas nor Hizebollah are ...," if people, by a margin of two to one, are making such constructions, sooner or later the descriptive grammar books will take notice. Fowler&fowler«Talk» 22:40, 3 May 2009 (UTC)

    I agree that "6" and "35" (in the sense used here) are each singular, as in "7 is a prime number" or "12 is a composite number". Per Bartleby's and other references, I feel that "neither...nor" should take a singular verb if both nouns are singular, as in "Neither Clara nor John was absent from class". Proteins (talk) 10:06, 5 May 2009 (UTC)

  • "Imagine a rectangular area a by b, and consider any common divisor c that divides both a and b exactly." Wikipedia is an encyclopedia, not an episode of Spongebob Squarepants. No sentence in an encyclopedia should start with "imagine."

    I presume that you are not objecting to the imperative mood (a staple of mathematics: "Let x be..."), just the verb "imagine". I re-worded this to use "consider" for both: "Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly." Since this is an encyclopedia, we should both strive to keep our comments less colorful. Proteins (talk) 10:32, 4 May 2009 (UTC)

  • "the GCD(462, 1071) = 3×7" In all other instances thus far, you have chosen not to use an article before GCD. Did you mean to say "then GCD(462, 1071) = 3×7"?

    Thank you for catching that inconsistency, which I've fixed. Proteins (talk) 10:32, 4 May 2009 (UTC)

  • "Integer factorization is thought to be a difficult problem for large numbers." A bit weaselly, and it's not particularly difficult if you have a calculator handy. Perhaps "can be" instead of "is thought to be" ?

    I clarified the sentence, although perhaps I should have been more clear about "large numbers". A pocket calculator might help in factoring numbers up to 20,000 (5 digits), but it won't be useful in factoring numbers with 500 digits, the rough size of number used in modern cryptography. Nevertheless, the Euclidean algorithm can quickly find the greatest common divisor of two 500-digit numbers. That was the point I was trying to convey. Should I spell that out in the article, do you think? Proteins (talk) 10:32, 4 May 2009 (UTC)

    I corrected the statement the first time from asserting "is a difficult problem" to "is thought to be..." since it is "only" thought to be difficult, not proven. The new version which states "The computational difficulty of integer factorization grows exponentially with the size of the number being factored" is a step backwards in that regards. The computational difficulty of integer factorization is in fact unknown. --C S (talk) 11:36, 4 May 2009 (UTC)

    You are right that I was inferring too much about the specific scaling of factorization. I've re-worded this sentence to "Factorization of large integers is believed to be such a difficult problem that many modern cryptography systems are based upon it.", which is supported by the Schroeder reference. Proteins (talk) 13:59, 4 May 2009 (UTC)

    Good enough for me. --Cryptic C62 · Talk 00:57, 8 May 2009 (UTC)

  • "A more subtle definition of the GCD is helpful in advanced mathematics, particularly ring theory." This statement should probably be accompanied by a ref.

    OK. Proteins (talk) 10:32, 4 May 2009 (UTC)

  • "GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c)" Shouldn't this also include " = GCD(GCD(a, c), b)"?

    If only for symmetry. Good catch! Proteins (talk) 10:32, 4 May 2009 (UTC)

  • "Thus, Euclid's algorithm, which computes the GCD of two numbers, suffices to calculate the GCD of arbitrarily many numbers." Odd wording at the end. Suggest switching to "integers" to allow the following rewrite: "Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of any number of integers."

    That's a good point and a good rewording. By using the word "number", I was trying to be general, since this result applies not only to integers, but to any number system for which the EA works, such as real numbers or Gaussian integers. Proteins (talk) 10:32, 4 May 2009 (UTC)

    Well, if you'd still like to stick with "numbers" rather than "integers", how about this: "Thus, Euclid's algorithm, which directly computes the GCD of two numbers, can be used to calculate the GCD of any group of numbers, regardless of the size of the group." Or something? As long as we avoid phrases like "number of numbers", it should be fine. --Cryptic C62 · Talk 18:52, 4 May 2009 (UTC)

  • "This approach begins by showing that, if the theorem holds for n, it also holds for n + 1." I just learned about induction last semester, and this doesn't seem to be quite right, specifically the last two clauses. My understanding of induction is that it is a two-step process. The first step is proving the basis case (usually n=0 or n=1), and the second step is proving that it holds for n+1. The sentence in question is written as though the first step proves the second step, which is not the case.

    For induction, it doesn't matter whether you prove the basis case first and the (n implies n+1) step second, or the reverse. I chose to present the method in the reverse order because (1) I thought it would be easier for lay-people to follow, (2) it emphasizes the (n implies n+1) step, which I feel is more important; and (3) it de-emphasizes the basis case and clarifies that a proof could start with any basis case, e.g., n=7. Proteins (talk) 09:36, 5 May 2009 (UTC)

    Hmm. I've reread that section, and I'm not sure why I had a problem with it the first time, as it makes perfect sense to me now. Perhaps I should have read the entire section before commenting on individual sentences... --Cryptic C62 · Talk 16:31, 5 May 2009 (UTC)

  • "A recursion is an equation relating numbers that form a series a1, a2, a3, etc." This is a very poor definition of a recursion, as it does not adequately explain the concept to a reader with no prior familiarity to it. How about "A recursion is an equation in which a_n, an arbitrary term in a series, is defined by the values of previous terms in the series, such as a_n-1 or a₀". This will also help the reader understand the Fibonacci example a bit more clearly.

    That's a good suggestion. I've re-worded the recursion along these lines. Proteins (talk) 09:36, 5 May 2009 (UTC)

  • "Several equations associated with the Euclidean algorithm are recursive, such as r_k = r_k−2 − q_kr_k−1." This example is essentially useless, as neither the meaning of the equation nor the terms used therein have been defined yet.

    Eliminated foreshadowing. Proteins (talk) 09:36, 5 May 2009 (UTC)

  • "Finally, in infinite descent, a given solution is used to construct a smaller solution." I read this sentence and thought I understood the concept being explained. Then I read infinite descent. Then I reread this sentence, which I now realize does a fairly poor job of explaining infinite descent. My familiarity with the concept is limited to that which I have just read, so I have no suggestion as to how to concisely summarize it, but I strongly urge you to rework the current explanation.

    I hadn't wanted to talk about the (more common) use of infinite descent in impossibility proofs such as Fermat's Last Theorem. Rather, my goal was to prepare the reader to follow the logic of why the EA must stop eventually. Nevertheless, I've re-written those sentences to to give a broader understanding of the argument. Proteins (talk) 09:36, 5 May 2009 (UTC)

  • "The validity of the Euclidean algorithm can be shown by two-step argument." Since the title of the section is proof of validity, perhaps this sentence should include the word 'proof': "The validity of the Euclidean algorithm can be proven with a two-step argument."

    I had avoided that wording for fear that mathematicians would cavil that the "proof" was not rigorous. I prefer your wording, however, so I replaced it. Proteins (talk) 16:58, 5 May 2009 (UTC)

    If you're worried about what mathematicians will think of the section, perhaps providing a rigorous proof would be better than simply avoiding the word 'proof'. In any case, I'm happy with it as is. --Cryptic C62 · Talk 18:04, 5 May 2009 (UTC)

  • "This agrees with the GCD(1071, 462) found by prime factorization above." Erm, there is no mentions of 1071 or 462 in the Background section. Why not just give the prime factorization here?

    Perhaps I'm not following you but the the paragraph about prime factorization and GCD in the Background section uses 1071 and 462 as an example. For example, it says, "since 462 can be factored into 2×3×7×11 and 1071 can be factored into 3×3×7×17, the greatest common divisor of 462 and 1071 equals 21 = 3×7, the product of their shared prime factors." We could repeat that here, but it seems redundant. Proteins (talk) 16:58, 5 May 2009 (UTC)

    >.< I swear you put that in after I made the comment! :P --Cryptic C62 · Talk 18:04, 5 May 2009 (UTC)

  • "The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly." This paragraph desperately needs to end with: "The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle." or something like that.

    Excellent suggestion, thanks! Proteins (talk) 17:04, 5 May 2009 (UTC)

  • "where the magnitude of rk is strictly less than that of rk−1" The use of 'magnitude' here strikes me as being a bit odd. Why not just write a simple inequality? r_k < r_k-1

    The "magnitude" wording also covers versions of the algorithm when the remainder can be negative. For example, -37628 < 4, but 4 has a smaller magnitude. Proteins (talk) 16:58, 5 May 2009 (UTC)

    True. I wonder if using absolute value notation |r_k| would be better. Up to you. In any case, magnitude or absolute value should be linked to avoid confusion for math noobs. --Cryptic C62 · Talk 18:04, 5 May 2009 (UTC)

    Another good idea, which I followed. Proteins (talk) 02:29, 6 May 2009 (UTC)

  • "Euclid finds the quotient and remainder by repeated subtraction" Last time I checked, Euclid is dead. Past tense, perhaps?

    Perhaps passive voice, instead. Proteins (talk) 16:58, 5 May 2009 (UTC)

    Perhaps I've struck the issue. --Cryptic C62 · Talk

  • "r_k ≡ r_k−2 mod r_k−1" Is there some article to which we can link '≡'? I'm not sure I know what it means.

    It means "equivalent to" in modular arithmetic. I'll make a link. Proteins (talk) 16:58, 5 May 2009 (UTC)

  • I don't think the implementations section belongs in this article. Wikipedia is not a how-to guide, and this section does not contain any new relevant information.

    Your initial reaction is similar to mine. Bu let me argue that the implementations contribute at least epsilon to the article for most readers, and for some readers may convey the algorithm's idea better than anything else. I note that when I arrived at this article — then rated at nearly GA level by the Math WikiProject — the implementations were the article's main content, having been debated and perfected for over seven years. Some editors champion the pseudocode as the only valid way of defining the algorithm precisely. In deference to these editors and in deference to the many readers like them, I feel we should retain the Implementations section. Proteins (talk) 03:18, 9 May 2009 (UTC)

    Deference to these editors? Pfft. Perhaps you have forgotten the disclaimer: "If you don't want your writing to be edited mercilessly or redistributed for profit by others, do not submit it." As for the readers, they come here for a lot of things that they really shouldn't (medical advice comes to mind). The very most we can do in regards to instruction content like this is to provide an informative link — perhaps to a WikiHow article or a programming site. I realize that you have the best intentions by wanting to keep the material, but the fact of the matter is that it really doesn't belong here. The other points you've brought up are largely irrelevant. --Cryptic C62 · Talk 03:32, 9 May 2009 (UTC)

    Let me clarify the question with a triple negative. ;) I'm NOT saying that we should violate WP:NOT in order to NOT hurt the feelings of some devoted editors. Rather, the pivotal issue is whether the Implementations section allows us to explain the algorithm to readers who might not really understand it otherwise. I argue yes. It's not about providing snippets of HOWTO code, but rather providing another avenue that connects the algorithm to our readers. Proteins (talk) 04:13, 10 May 2009 (UTC)

    You will not be able to find a pseudocode representation that all programmers will be able to understand. I am very experienced with TI-BASIC and I've twiddled with C++, but I'm not familiar with some of the notation you've used. As I see it, you have three options: Give whatever programming language you choose WP:UNDUE weight by explaining all of the relevant syntax, leave it vague and hope for the best, or remove the section altogether. I think at this point it's clear which option I'd prefer. --Cryptic C62 · Talk 03:32, 11 May 2009 (UTC)

  • "if the resulting negative remainder is smaller in absolute value than the typical positive remainder" You used "magnitude" earlier. I recommend swapping out "absolute value" for "magnitude" for consistency.

    OK, sounds good. Proteins (talk) 03:18, 9 May 2009 (UTC)

  • "to the greatest length g that measures a and b evenly" The word "measures" seems a bit off. Shouldn't it be "divides"?

    A geometric length is qualitatively different than an integer. "Measure" or "measure off" is the standard vocabulary used for the former. The ancient Greeks distinguished the two operations (division and "measuring off"), and their concepts have carried over. Proteins (talk) 03:18, 9 May 2009 (UTC)

  • "in other words, the lengths a and b are both multiples of the length g" I suggest the injection of the word "integer" before "multiples", without it, the whole concept is meaningless.

    Great catch, although I predict that most non-mathematicians would assume that "multiple = integer multiple". Proteins (talk) 03:18, 9 May 2009 (UTC)

    Aye, it's the finnicky mathematicians I'm worried about here. :) --Cryptic C62 · Talk 03:32, 11 May 2009 (UTC)

  • "The algorithm was likely known by Eudoxus of Cnidus (about 375 BC). The use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in Euclid and Aristotle (Topics IV) suggests that the algorithm predates Eudoxus." I see what you're getting at, but to some readers, these sentences may seem to contradict each other. Suggested rewrite: "The use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in Euclid and Aristotle (Topics IV) suggests that what we now know as the Euclidean Algorithm may have predated Eudoxus of Cnidus, a Greek mathematician who died in approximately 350 BC." or some such. Meh. That's not exactly perfect either. Give it some thought.

    That's a good suggestion, and very helpful. I toyed with the wording beforehand, but I didn't come up with anything as good as yours. I've uploaded a third wording that may combine the best of our efforts. Proteins (talk) 04:13, 10 May 2009 (UTC)

    Ah, much better! More direct than mine, too. I'm confused about the last bit, though: "use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in Euclid and Aristotle (Topics IV)" Did Euclid and Aristotle collaborate on a book called "Topics IV"? What's going on here? --Cryptic C62 · Talk 03:32, 11 May 2009 (UTC)

    That interpretation didn't occur to me, thanks! The Topics reference was just a clue for the reader where to find Aristotle's comments on reciprocal subtraction. Euclid and Aristotle didn't co-author anything, at least to my knowledge; IIRC, Euclid was much younger than Aristotle. The passage now reads "The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle." Proteins (talk) 15:57, 14 May 2009 (UTC)

  • "Euclid's algorithm was re-invented both in India and in China" "re-invent" often implies that an existing concept was significantly improved. I think "independently developed" or "independently discovered" might serve better.

    Good idea, made additional minor changes in wording. Proteins (talk) 03:35, 9 May 2009 (UTC)

  • "the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer"" Erm... why?

    Good question! The historical record does not say, as far as I can tell. One author speculates that it's because the algorithm "pulverizes" difficult linear Diophantine equations in only a few steps, emphasizing its power to solve problems. Its operation also vaguely resembles a pulverizer that breaks a large stone into medium-sized stones, then into small stones, and thence into dust. Proteins (talk) 03:35, 9 May 2009 (UTC)

    Both of those certainly make sense. Whichever explanation best adheres to the available sources should probably be added to the article—I'm sure some readers will have the same question I did. --Cryptic C62 · Talk 03:32, 11 May 2009 (UTC)

    Added "perhaps because of its effectiveness in solving Diophantine equations." with a citation to the speculating textbook. Proteins (talk) 16:00, 14 May 2009 (UTC)

  • "and applied it solving linear Diophantine equations" Consider changing "applied it solving" to "used it to solve".

    Much better, thank you! Proteins (talk) 03:35, 9 May 2009 (UTC)

  • "Although a special case of the Chinese remainder theorem was described earlier by Chinese mathematician and astronomer Sun Tzu" The use of "earlier" implies a relation to the previous sentence rather than the following clause. Suggest "was described earlier" to "had already been described".

    Good! Proteins (talk) 03:35, 9 May 2009 (UTC)

  • "The algorithm was first described in Europe in the second edition of Bachet's Problèmes plaisants et délectables (1624)." Which algorithm? The EA? Or the Chinese Remainder Theorem? Also, do you have a translation for that French title?

    Clarified EA, translated title. Proteins (talk) 03:35, 9 May 2009 (UTC)

  • "In the 19th century, Carl Friedrich Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers by 1815 (published 1832), although he did not mention the algorithm in his earlier work, Disquisitiones Arithmeticae (1801), except as a method for continued fractions." If you include specific years, "In the 19th century" is redundant. Also, I'm confused by the 1815/1832 thing. Also, the second chunk is somewhat misleading. Suggested rewrite: "though he had mentioned the algorithm in his earlier work, Disquisitiones Arithmeticae (1801), simply as a method for solving continued fractions."

    Yes, this was worded awkwardly. I've re-arranged the material and added a topic sentence so that it flows better (I hope). The 1815/1832 issue is that Gauss did the calculation in 1815 (as we know from his notebooks), but didn't publish it until 1832. Proteins (talk) 06:42, 11 May 2009 (UTC)

    Ah, so much better! --Cryptic C62 · Talk 23:06, 11 May 2009 (UTC)

  • "Dirichlet seems to have..." A person's full name (or at least their first name) should be given the first time they are mentioned.

    OK, Peter it is. Proteins (talk) 06:42, 11 May 2009 (UTC)

  • "would hold true for any other system of numbers in which the Euclidean algorithm could be applied" Should be "to which the", right?

    Right on! thanks, 06:42, 11 May 2009 (UTC)

  • "Dirichlet's insight likely inspired Richard Dedekind to develop theories for new types of numbers, the algebraic integers, and more generally Euclidean domains." As this is written, it implies that Dedekind might or might not have developed those theories. Also, the ending construction implies that "new types of numbers, the algebraic integers, and more generally Euclidean domains" are all separate items in a list, but my hunch is that the second is an example of the first. Suggested rewrite: "Richard Dedekind's theories for new types of numbers, such as algebraic integers and Euclidean domains, may have been inspired by Dirichlet's insight." If you do end up rewriting this sentence, be sure to tweak the following sentence to make sure it flows logically.

    I made a draft - does it read better now? Proteins (talk) 06:42, 11 May 2009 (UTC)

    Looks very good up until this sentence: "Dedekind also defined the concept of a Euclidean domain, a number system in which (roughly speaking) a version of the Euclidean algorithm can be defined." Unfortunately, the speaking is so rough that I have no idea what it means. "(roughly speaking)" is unencyclopedic, and the statement that follows doesn't provide any real information.

    I changed the wording slightly to "Dedekind also defined the concept of a Euclidean domain, a number system in which a version of the Euclidean algorithm can be defined (as described below)." I'm hoping that the wikilink to the fuller explanation within the article itself will satisfy the readers' curiosity. Proteins (talk) 16:04, 14 May 2009 (UTC)

    That's better, but the wording is still a bit odd. "...in which a version of the Euclidean algorithm..." isn't worded in the best possible way, as it leaves the reader thinking "Uhh... what version?" Any adjective before "version" would make this read more smoothly.

    Perhaps "generalized version"? I don't want to have to go into details in the hHistory section about how we need to define the norm and the definition of divisibility in the new sumber system to make an EA work there. Proteins (talk) 14:11, 16 May 2009 (UTC)

  • "In 1829, Sturm showed..." Not sure why this chunk comes after the Dirichlet/Dedekind bit. I'm assuming that Dirichlet/Dedekind did their work after 1832, which may not be correct. If that is correct, then this section is somewhat out of order. If is not correct, then this is still out of order and specific years should be added for clarity (if possible).

    I was trying to discern between two developments of the EA in the 19th century: the general development of new number systems and specific applications of the EA such as Sturm's theorem. Proteins (talk) 06:42, 11 May 2009 (UTC)

    Ah. This distinction is clearer now. --Cryptic C62 · Talk 23:06, 11 May 2009 (UTC)

  • "In 1829, Sturm showed that the algorithm provided an efficient method for counting the number of real roots of polynomials in any given interval." Again, be sure to include given names when introducing people. Also, "efficient method" is currently linked to Sturm chain. WP:MOSLINK advises that the article being linked to should be made clear by the words being linked. In this case, I fully expected the phrase to link to an article about the efficiency of algorithms. I suggest rewording the sentence to include "Sturm chain" and then linking that directly.

    Both good calls. I added "Charles" to Sturm, and I re-arranged the sentence to clarify the Sturm-chain method. I also removed a double link within the paragraph. Proteins (talk) 16:26, 14 May 2009 (UTC)

  • "A generalization of this result is known as Sturm's theorem." The use of the indefinite article "a" implies that there are multiple generalizations of the result, in which case I would recommend swapping out "a" with "one" or explaining the other generalizations. Or both. If this is the only significant generalization, I recommend swapping out "a" for "the". I wouldn't worry about it too much though; if the number of pertinent generalizations was not made clear in your research, "a" will do just fine.

    Since it wasn't really germane to the EA itself, I dropped the "generalization" sentence. I might add another EA application later, though, to flesh out that paragraph somewhat. Proteins (talk) 16:26, 14 May 2009 (UTC)

  • "No new general algorithms were developed until 1979" Erm, I seriously doubt this. I think you may need something more specific than "general algorithms".

    Reworded to be briefer and to keep within the bounds of the references. Proteins (talk) 16:26, 14 May 2009 (UTC)

  • "The PSLQ algorithm, a "jazzed up" version of Euclid's algorithm, has been recognized as one of the top ten algorithms of the 20th century." This is totally irrelevant trivia and really doesn't fit in with the section.

    Yes, I should've listened to my conscience on this one. Gone. Proteins (talk) 16:26, 14 May 2009 (UTC)

  • I'm not sure that the Game of Euclid section belongs in the Historical development section. It does seem to be worth mentioning in the article, but it really doesn't fit in with the content introduced here. It might be better off being listed in the See Also section.

    Another difficult call. I sympathize with the critique, but I'm not sure where else to put the discussion. Hitherto I've included the discussion and early in the article, because it's mentioned prominently in some textbooks, it's been the subject of a few research papers, and because I suspect that it might help make some readers more comfortable with the topic, less daunted by the otherwise unbroken wall of math and more likely to push on. Proteins (talk) 16:26, 14 May 2009 (UTC)

  • It seems odd that the Bezout's identity section is a subsection of Applications. Applications sections, in my (probably biased) experience, generally deal with how the subject applies to real world problems, not theoretical mumbo jumbo. Some readers will probably jump down to Applications thinking that they are going to be reading about how the EA can be used in sailing or accounting or whatever. To avoid crushing their tiny little hearts, consider changing Applications to Mathematical applications, though I may be alone in thinking that this is a good idea.

    That does seem like a good suggestion; more specific section headings are always better. Changed to "Mathematical applications". Proteins (talk) 14:11, 16 May 2009 (UTC)

  • "to the set of multiples of a single number, their GCD g" This would probably be slightly less confusing if "a single number, their GCD g" were replaced with "GCD(a, b)". Much simpler.

    Excellent idea; changed wording as you suggest. Proteins (talk) 01:39, 18 May 2009 (UTC)

  • "For example, suppose that a cook has two measuring cups of volume a and b, respectively. By adding and subtracting multiples of these two volumes, the cook can measure out any volume ua + vb. These volumes are all multiples of g = GCD(a, b)." Although I appreciate the real world connection, the inclusion of the cook is somewhat unnecessary and unencyclopedic. This analogy should work with just the measuring cups.

    Good point; I hope you like the new wording. Thanks for your continued keen reviewing! Proteins (talk) 01:39, 18 May 2009 (UTC)

  • "For example, consider two measuring cups of volume a and b, respectively" Why "respectively"?
  • "By assumption, this can be written as" I've never heard the term "by assumption" before. If it is indeed the correct term here, perhaps it should be wikilinked.
  • The closing lines of Extended Euclidean algorithm (before Equivalent matrix method) are, to borrow a term of yours, a "wall of math". I think an example with real numbers would be very helpful here, something I'm sure you can find in any math textbook.
  • The term matrix should probably be wikilinked somewhere in the section Equivalent matrix method.
  • "The inverse is well-defined" I have the feeling "well-defined" is jargon that should either be wikilinked, explained, or reworded.
  • "Bézout's identity is essential to many higher applications" I think "higher" was supposed to be "higher-level", though omitting it entirely would also work.
  • "For if the greatest common divisor of u and w is 1, then integers s and t can be found such that" Extraneous "for" at the beginning of this sentence? Perhaps I'm misreading this section.
  • "Specifically, if a prime number p divides L, it must divide at least one factor of L" If you want to introduce a new letter for this sentence, be sure to actually use it: "Specifically, if a prime number p divides L, p must divide at least one factor of L". One the other hand, if you want to be brief and reduce the number of letters being thrown at the reader, try this: "Specifically, if a prime number divides L, it must divide at least one factor of L" or "Specifically, if a prime number p divides L, that prime number must also divide at least one factor of L".
  • "where a, b and c are also integers" It may be helpful for the reader if "also" were swapped out for "given". This clarifies the distinction between the variables (x, y) and the constants (a, b, c).
  • "where s and t can be found by the extended Euclidean algorithm" Throughout the article, you've mentioned several times how the EA is extremely helpful in solving Diophantine equations. However, this is the only line (along with the bit about Bezout's identity, although that is arguably a separate topic) of the section Linear Diophantine equations that mentions the EA. Perhaps I may be missing something here, but it seems to me that whatever connections exist between the EA and linear Diophantine equations need to be spelled out more explicitly in this section.

--Cryptic C62 · Talk 19:59, 3 May 2009 (UTC)

Thank you very much for your careful reviewing! The article is definitely improving. Proteins (talk) 10:32, 4 May 2009 (UTC)

Comments

1) The spacing convention is not followed consistently through out. (e.g. 252 = 21 × 12 (with space) but 35 = 5×7 (without space), k=0 (with no space))

Thank you; I tried to be consistent about this, but a few expressions may have escaped my notice. I'll go through the article myself, but please correct any unspaced expressions that you happen to see. The spaced version (using a non-breaking space) is the correct one. Proteins (talk) 21:48, 10 May 2009 (UTC)

2) "Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of an arbitrary number of integers."

Can it calculate the GCD of a countable infinite set of integers? An uncountable one? Be specific.

You're pulling my leg about the uncountably infinite set of integers, right? I may not be a mathematician, but I wasn't born yesterday. ;) How about "arbitrarily many integers" as a compromise wording? Proteins (talk) 21:48, 10 May 2009 (UTC)

3) "The latter argument is used to show that the Euclidean algorithm for natural numbers must end in a finite number of steps."

Citation needed.

OK, citation provided. Proteins (talk) 21:48, 10 May 2009 (UTC)

4) Redundant phrase (found a lot at the beginning of paragraphs):

• "the Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD)"
• "The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b."
• "Euclid's algorithm, which computes the GCD of two integers"
• "The Euclidean algorithm finds the greatest common divisor g of two numbers a and b in a series of steps."

131.111.216.15 (talk) 15:58, 8 May 2009 (UTC)

I write that way on purpose to provide a touchstone, a "red thread" running through the article for newcomers to grab onto. I may have overdone it, however. I'll go through the article and try to trim the unnecessary. Proteins (talk) 21:48, 10 May 2009 (UTC)

The above discussion is preserved as an archive. Please do not modify it. No further edits should be made to this page.