Knowledge (XXG):Featured article candidates/Euclidean algorithm/archive1

738:"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"). 938:

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. --

3205:"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. 324:

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?

1225:. 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.) 3119:"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." 857:). 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. -- 214:

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. --

2880:"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 441:

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. --

2230:"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. 872:

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

426:, 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. 3367:." 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. 309:" 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. -- 3524:"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. 3283:"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). 361:, 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". -- 595:

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

1251:? 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 2190:"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." 1353:- 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. 1877:"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. 353:, 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 3651:"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 1947:"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 2508:"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. 351: 3436:

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

2932:

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

2760:

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

1277:

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

658:

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

643:

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

167:

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?

2094:

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

1737:

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

1495:

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

871:

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

766:

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

613:

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 Knowledge (XXG). Information presented in Knowledge (XXG) should be easily verifiable by anyone who wishes to do so. To

502:

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,

395:

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

358: 323:

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

134:

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

2472:

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

2397:. 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. 1395:

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

937:

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

349:

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

2987:

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

1371:

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

440:

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

1476:

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

1083:

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.

922:

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

290:

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.

213:

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

2722:

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

1995:

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

190:

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

737:

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)

594:

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

3225:

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

2209:

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

1619:

to people using standard screen readers. Perhaps the best long-term solution for Knowledge (XXG) 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

628:

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

2109:

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

1292:

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

837:

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

3065:"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". 2079:

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.

143:. Although the oldest known algorithm (23 centuries), it continues to play a role in developing new mathematics. It would be helpful for Knowledge (XXG) to have an excellent article on this topic, both for itself and for the introduction it provides to advanced mathematics such as 1517:. 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 1293:

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 :-). --

3712:

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.

3341:

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

3251:

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.

2289:"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 1688:." 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 2818:

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.

529:

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 Knowledge (XXG) requires us to follow and that means the picture is considered in the public domain in the US (see

3333:"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 1807:

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

952:

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

3125:

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.

691:

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

1149:

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.

575:

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.

1396:

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.

1334:. 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. -- 2021:"Imagine a rectangular area a by b, and consider any common divisor c that divides both a and b exactly." Knowledge (XXG) is an encyclopedia, not an episode of Spongebob Squarepants. No sentence in an encyclopedia should start with "imagine." 1278:

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.)

2740:

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

2194:

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.

2695:

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

1971:(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 2723:

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. --

2704:. 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. 629:

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. --

2956:"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. 2029:(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 1614:

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

1477:

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).

3820:

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.

2268:

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...

3255:

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.

3409:"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. 741:

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.

91: 2075:"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" ? 3655:

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

2080:

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?

2890:

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.

2787:"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. 823:? 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? 480:- 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. 98: 3737:

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?

2745:

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.

2444:

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. --

2405:. 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. 1781:

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.

1445:

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.

472:- 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. 1743:

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?

3462:. 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 1598:. 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. -- 599:, 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. -- 1103:

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.

802:

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.

3002:

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. --

262:

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. --

1907:- 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. 709:

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.

614:

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.

350:

of the Euclidean algorithm being the oldest algorithm (with no qualification). Perhaps Knowledge (XXG) itself has had a role in perpetuating this. In "Mathematica in Action" by Stan Wagon

3582:"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. 3433:

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.

3499:"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. 2838:"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. 1273:

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

396:

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. --

2765:

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. --

3648:

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).

1740:

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.

677:

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.

3371:

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.

1964: 1757:

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? --

2393:"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 2242:+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 ( 238:

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. --

3466:

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

838:"division algorithm", merely calling it division with remainder at times), Dummit & Foote's abstract algebra book states that the "Euclidean algorithm" comes from the 3562:) 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. 2700:

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

1372:

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. --

800: 255:

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

3346:

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.

2529:"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 380:"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 ? -- 3551:"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. 902:(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! 3613:". 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 1777:"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 40: 2540:

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.

854:

article, which was published in the Bulletin of the American Mathematical Society in 1949, also uses the term Euclidean algorithm for division algorithm (see

3579:"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. 2148:"A more subtle definition of the GCD is helpful in advanced mathematics, particularly ring theory." This statement should probably be accompanied by a ref. 3388:"No new general algorithms were developed until 1979" Erm, I seriously doubt this. I think you may need something more specific than "general algorithms". 2430:

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.

515:; 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. 3707:

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))

1837:, are unrelated, which is obviously never the case. "other" makes it clear that the concepts are unrelated to EA without introducing the ambiguity. -- 894: 884: 879: 954: 899: 874: 659:

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. --

2250:+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., 986:

I understand and agree wholeheartedly. Perhaps I should have forestalled your comments by mentioning that Herstein is still a widely used book. --

889: 30: 17: 1852:

Just to clarify, the wording now is "although the latter notation is also used for other mathematical concepts, such as two-dimensional vectors."

3437:

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.

1829:

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,

1473: 3802: 548:

We can use the the French Lamé. As CS explains, it is acceptable under US copyright law. You can upload it to the English Knowledge (XXG).

2426:, perhaps this sentence should include the word 'proof': "The validity of the Euclidean algorithm can be proven with a two-step argument." 3731:

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

2050:"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 "the 3830: 3810: 3771: 3747: 3722: 3691: 3672: 3539: 3514: 3489: 3446: 3422: 3401: 3380: 3355: 3321: 3306: 3265: 3246: 3220: 3181: 3150: 3135: 3109: 3080: 3055: 3026: 3012: 2997: 2971: 2942: 2923: 2900: 2884:, a Greek mathematician who died in approximately 350 BC." or some such. Meh. That's not exactly perfect either. Give it some thought. 2868: 2853: 2828: 2802: 2775: 2755: 2733: 2713: 2675: 2607: 2582: 2568: 2549: 2521: 2498: 2482: 2454: 2439: 2414: 2385: 2327: 2279: 2263: 2220: 2204: 2182: 2161: 2134: 2119: 2104: 2089: 2067: 2042: 2005: 1990: 1931: 1916: 1899: 1861: 1847: 1824: 1802: 1767: 1752: 1713: 1680:

Apparently you missed the sentence "In the 19th century, the algorithm was generalized to other types of numbers, which led to modern

1649: 1629: 1605: 1505: 1486: 1454: 1440: 1422: 1413:

I didn't follow the thread of edits, but talking to the reader ("imagine ...") and "we" should be avoided as unencyclopedic language.

1408: 1381: 1362: 1343: 1316: 1302: 1287: 1268: 1234: 1215: 1194: 1175: 1159: 1131: 1112: 1093: 1070: 1052: 1032: 995: 972: 947: 932: 913: 866: 832: 813: 751: 732: 718: 686: 668: 653: 638: 623: 608: 585: 557: 543: 524: 494: 450: 435: 405: 389: 370: 333: 318: 300: 285: 271: 247: 223: 200: 177: 156: 82: 3191:"would hold true for any other system of numbers in which the Euclidean algorithm could be applied" Should be "to which the", right? 3576:"The inverse is well-defined" I have the feeling "well-defined" is jargon that should either be wikilinked, explained, or reworded. 1145:. Overall, the article is excellent and it certainly meets criteria 1 and 2. In fact, arguments could be made that the article is 3480:

That does seem like a good suggestion; more specific section headings are always better. Changed to "Mathematical applications".

357:

algorithm bar none. However, misleadingly, the section heading proceeding the passage states "The oldest surviving algorithm"! In

114: 259:

algorithm" that has survived to the present day. Since Knuth actually wrote an article in 1972 on ancient Babylonian algorithms

3756:

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

2372:." This example is essentially useless, as neither the meaning of the equation nor the terms used therein have been defined yet. 1921:

Hrm. Well, I'm not particularly sure about it myself, so use your best judgment. I just wanted to bring it to your attention. --

2905:

Ah, much better! More direct than mine, too. I'm confused about the last bit, though: "use of the technical term ἀνθυφαίρεσις (

1431:

is ok with limited usage of this type. If MOSMATH is inconsistent with FA, that's a shame. Feel free to edit my version. --

2558:| would be better. Up to you. In any case, magnitude or absolute value should be linked to avoid confusion for math noobs. -- 1307:

These are good suggestions! I've added some textbook references to the "Induction, recursion and infinite descent" section.

423: 3017:

Added "perhaps because of its effectiveness in solving Diophantine equations." with a citation to the speculating textbook.

2095:

factored" is a step backwards in that regards. The computational difficulty of integer factorization is in fact unknown. --

119: 3237:)." I'm hoping that the wikilink to the fuller explanation within the article itself will satisfy the readers' curiosity. 2594:"Euclid finds the quotient and remainder by repeated subtraction" Last time I checked, Euclid is dead. Past tense, perhaps? 3094:(1624)." Which algorithm? The EA? Or the Chinese Remainder Theorem? Also, do you have a translation for that French title? 2464:"This agrees with the GCD(1071, 462) found by prime factorization above." Erm, there is no mentions of 1071 or 462 in the 850:

Euclidean algorithm. Herstein is a pretty well-known algebra book, so I dug a bit more and I found that a source on the

3597:" If you want to introduce a new letter for this sentence, be sure to actually use it: "Specifically, if a prime number 3166:

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

1672:

The lead does not adequately summarize all of the main sections of the article. Unless I am misreading, it appears that

2933:

the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle."

2812:"to the greatest length g that measures a and b evenly" The word "measures" seems a bit off. Shouldn't it be "divides"? 3040:"and applied it solving linear Diophantine equations" Consider changing "applied it solving" to "used it to solve". 2718:

Deference to these editors? Pfft. Perhaps you have forgotten the disclaimer: "If you don't want your writing to be

1985: 1968: 1602: 1210: 967: 908: 808: 674: 531: 1418: 1283: 1230: 469: 276:

I've read the quote in the box. Is this "only" Knuth's opinion or a statement on whom most specialists agree ? --

3806: 2422:"The validity of the Euclidean algorithm can be shown by two-step argument." Since the title of the section is 2844:

Great catch, although I predict that most non-mathematicians would assume that "multiple = integer multiple".

2981:"the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer"" Erm... why? 2473:

21 = 3×7, the product of their shared prime factors." We could repeat that here, but it seems redundant.

1000:

I have added the following as a footnote to the introductory sentence: Some widely-used textbooks, such as

3794:"The Euclidean algorithm finds the greatest common divisor g of two numbers a and b in a series of steps." 2402: 2169:"GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c)" Shouldn't this also include " = GCD(GCD(a, c), b)"? 1274: 1240: 3668: 3317: 3146: 3008: 2919: 2864: 2771: 2729: 2618: 2564: 2494: 2450: 2401:

I hadn't wanted to talk about the (more common) use of infinite descent in impossibility proofs such as

2275: 2216: 2130: 1927: 1843: 1763: 1665: 1599: 1190: 747: 649: 619: 581: 1980: 1205: 962: 903: 803: 3788:"The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b." 923:

used (mainly by the top graduate programs and more that like to think they are in the same class). --

1414: 1279: 1226: 140: 3338: 1428: 3734:

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

3234: 1252: 1023:

I don't know if that's the best place for it, but it should save some confusion on terminology. --

64: 1616: 511:. I found an alternative photograph of Dedekind published in 1930 in Braunschweig as part of his 3826: 3767: 3743: 3718: 3687: 3535: 3510: 3485: 3442: 3418: 3397: 3376: 3351: 3302: 3261: 3242: 3216: 3177: 3131: 3105: 3076: 3051: 3022: 2993: 2967: 2938: 2896: 2849: 2824: 2798: 2751: 2709: 2671: 2663: 2603: 2578: 2545: 2517: 2478: 2435: 2410: 2381: 2323: 2259: 2200: 2178: 2157: 2115: 2085: 2063: 2038: 2001: 1912: 1895: 1857: 1820: 1798: 1748: 1709: 1646: 1625: 1501: 1482: 1450: 1358: 1312: 1204:. I haven't read it yet, but it looks pretty good. Will make vote more definite upon reading. 1171: 1127: 1089: 1066: 1048: 1017: 828: 820: 728: 714: 553: 520: 490: 477: 431: 329: 296: 196: 152: 78: 3785:"the Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD)" 2913:

IV)" Did Euclid and Aristotle collaborate on a book called "Topics IV"? What's going on here? --

2762: 187: 1043:

I oppose anything that flashes. Sorry, I know it's cool but it's very distracting to readers.

3548:"For example, consider two measuring cups of volume a and b, respectively" Why "respectively"? 2988:

breaks a large stone into medium-sized stones, then into small stones, and thence into dust.

2881: 1155: 1108: 682: 485:

These issues should relatively easy to resolve. I look forward to reading the entire article.

385: 281: 243: 3233:, a number system in which a version of the Euclidean algorithm can be defined (as described 3664: 3364: 3313: 3230: 3142: 3004: 2915: 2860: 2767: 2725: 2614: 2560: 2490: 2446: 2394: 2271: 2212: 2126: 1979:

making such constructions, sooner or later the descriptive grammar books will take notice.

1923: 1839: 1759: 1701: 1697: 1689: 1685: 1681: 1661: 1256: 1248: 1186: 1185:- lack of citations for over 50% of the page means that it fails the citation requirements. 851: 743: 645: 615: 577: 144: 2687: 770: 596: 2026: 1641:- sources look okay, links not checked with the link checker tool, as it was misbehaving. 918:

I didn't check all those books publication dates, but certainly Lang's well-known classic

1936:

In my way of thinking, it depends how we are using "6" in the context. Since we say "6

3530:

Good point; I hope you like the new wording. Thanks for your continued keen reviewing!

1001: 504: 2314:". This will also help the reader understand the Fibonacci example a bit more clearly. 503:

or that the photographs themselves were not published until more recently. I found a

3822: 3763: 3739: 3714: 3683: 3682:

Thank you very much for your careful reviewing! The article is definitely improving.

3531: 3506: 3481: 3438: 3414: 3393: 3372: 3347: 3298: 3257: 3238: 3226:

unencyclopedic, and the statement that follows doesn't provide any real information.

3212: 3173: 3127: 3101: 3072: 3047: 3018: 2989: 2963: 2934: 2892: 2845: 2820: 2794: 2747: 2705: 2667: 2599: 2574: 2541: 2513: 2474: 2431: 2406: 2377: 2319: 2255: 2196: 2174: 2153: 2111: 2100: 2081: 2059: 2034: 1997: 1908: 1891: 1853: 1816: 1794: 1744: 1705: 1642: 1621: 1497: 1478: 1446: 1436: 1404: 1377: 1354: 1339: 1308: 1298: 1264: 1167: 1123: 1085: 1062: 1044: 1028: 991: 943: 928: 862: 824: 724: 710: 664: 634: 604: 549: 539: 516: 486: 446: 427: 401: 366: 325: 314: 292: 267: 219: 192: 173: 148: 136: 74: 53: 3289:

I was trying to discern between two developments of the EA in the 19th century: the

2658:" Is there some article to which we can link '≡'? I'm not sure I know what it means. 1793:)" notation, and swapped order of last two sentences in paragraph for better flow. 1151: 1104: 958: 678: 415: 381: 277: 239: 2335:"Several equations associated with the Euclidean algorithm are recursive, such as 855: 2234:

For induction, it doesn't matter whether you prove the basis case first and the (

3334: 2690:

a how-to guide, and this section does not contain any new relevant information.

3090:"The algorithm was first described in Europe in the second edition of Bachet's 1693: 1009: 3163: 2033:

an encyclopedia, we should both strive to keep our comments less colorful.

1244: 508: 306: 2318:

That's a good suggestion. I've re-worded the recursion along these lines.

260: 3229:

I changed the wording slightly to "Dedekind also defined the concept of a

1904: 2096: 1815:

That's a good suggestion! I followed your wording more-or-less exactly.

1432: 1400: 1373: 1335: 1294: 1260: 1024: 987: 939: 924: 858: 660: 630: 600: 535: 442: 411: 397: 362: 310: 263: 215: 169: 3392:

Reworded to be briefer and to keep within the bounds of the references.

1084:

Thanks! (We should continue this discussion on the article talk page.)

1166:

Thank you, and I hope that the copyright issues will now be resolved.

410:

The ancient Greek certainly knew about irrational numbers, at least as

2297: 1809: 2300:, is defined by the values of previous terms in the series, such as 1392:

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

39:

Subsequent comments should be made on the article's talk page or in

2858:

Aye, it's the finnicky mathematicians I'm worried about here. :) --

3780:

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

961:

does look recent. Anyway, this is not a biggie for me. Regards,

1963:

goes. If you look at usage on the web, "Neither * nor * is" has

3413:

Yes, I should've listened to my conscience on this one. Gone.

305:

I corrected this in the text before, but that is indeed what "

3474:, though I may be alone in thinking that this is a good idea. 2488:.< I swear you put that in after I made the comment! :P -- 2058:

Thank you for catching that inconsistency, which I've fixed.

1427:

Proteins is responsible for the "imagine". :-) In any case,

1061:

I've found a way to hide the animation until it's requested.

3791:"Euclid's algorithm, which computes the GCD of two integers" 3629:, that prime number must also divide at least one factor of 3429:

I'm not sure that the Game of Euclid section belongs in the

1944:

prime"), it seems to me we are thinking of it as singular.

1738:

would also be helpful to say "ten 12-by-12 square tiles".

124: 2468:

section. Why not just give the prime factorization here?

92:

Featured article candidates/Euclidean algorithm/archive1

3569:

should probably be wikilinked somewhere in the section

2701: 2697: 2210:

phrases like "number of numbers", it should be fine. --

57: 2962:

Good idea, made additional minor changes in wording.

2928:

That interpretation didn't occur to me, thanks! The

773: 819:

Perhaps you're referring to the "division lemma" or

99:

Featured article review/Euclidean algorithm/archive1

2909:, reciprocal subtraction) in Euclid and Aristotle ( 2554:True. I wonder if using absolute value notation |r 1239:Yet, is that not why we have separate articles on 794: 3840:The above discussion is preserved as an archive. 3297:applications of the EA such as Sturm's theorem. 1255:. I would suggest just adding some references to 1118:Thank you, and no worries! I just want to avoid 3505:Excellent idea; changed wording as you suggest. 139:(often used in electronic commerce) and solving 41:Knowledge (XXG) talk:Featured article candidates 43:. No further edits should be made to this page. 3846:No further edits should be made to this page. 3363:"A generalization of this result is known as 644:Euclid is something that I find interesting. 29:The following is an archived discussion of a 8: 2025:I presume that you are not objecting to the 1975:...," if people, by a margin of two to one, 18:Knowledge (XXG):Featured article candidates 3211:I made a draft - does it read better now? 3197:Right on! thanks, 06:42, 11 May 2009 (UTC) 1729:is the largest square tile that covers an 103: 1890:Excellent suggestion for the rewording. 1721:Caption: "The greatest common divisor of 1620:investment of time and effort, however. 955:Graduate Algebra: The Noncommutative View 900:Graduate Algebra: The Noncommutative View 772: 3617:, it must divide at least one factor of 3593:, it must divide at least one factor of 1879:Also, shouldn't it be "neither 6 nor 35 1016:, use "Euclidean algorithm" to refer to 3311:Ah. This distinction is clearer now. -- 505:similar image of Lamé published in 1897 106: 96: 89: 3621:" or "Specifically, if a prime number 3293:development of new number systems and 2573:Another good idea, which I followed. 1696:of one variable. This led to modern 1474:File:Euclidean algorithm 1071 462.gif 7: 1967:, whereas "Neither * nor * are" has 422:is devoted entirely to questions of 3609:must divide at least one factor of 2173:If only for symmetry. Good catch! 890:Problems in algebraic number theory 509:asserts its unrestricted copyrights 3092:Problèmes plaisants et délectables 880:Algebra: Groups, Rings, and Fields 24: 3585:"Specifically, if a prime number 2686:section belongs in this article. 2612:Perhaps I've struck the issue. -- 1470:Minor suggestion for improvement. 673:I agree with CS. Please re-read 3100:Clarified EA, translated title. 2598:Perhaps passive voice, instead. 1496:as the Arabic Knowledge (XXG). 1676:is not represented in the lead. 723:I've added 22 more references. 2512:Excellent suggestion, thanks! 1940:composite" (just as we say "7 507:, but the Ecole polytechnique 414:, even if they hadn't defined 1: 675:Knowledge (XXG):Verifiability 532:Knowledge (XXG):Public_domain 3653:Linear Diophantine equations 3556:Extended Euclidean algorithm 2662:It means "equivalent to" in 1965:approximately 7 million hits 1038:Comment on animation in lead 888:(2002), Murty and Esmonde's 846:does indeed call the above, 3458:section is a subsection of 1959:prime." That is as far as 1951:say, "The number of sheep ( 1399:Is this an improvement? -- 31:featured article nomination 3863: 2376:Eliminated foreshadowing. 1455:09:04, 30 April 2009 (UTC) 1441:08:02, 30 April 2009 (UTC) 1423:07:45, 30 April 2009 (UTC) 1409:07:11, 30 April 2009 (UTC) 1382:01:40, 30 April 2009 (UTC) 1363:01:18, 30 April 2009 (UTC) 1344:23:02, 29 April 2009 (UTC) 1317:18:47, 30 April 2009 (UTC) 1303:06:57, 30 April 2009 (UTC) 1288:06:16, 30 April 2009 (UTC) 1269:23:02, 29 April 2009 (UTC) 1235:21:47, 29 April 2009 (UTC) 1216:12:28, 29 April 2009 (UTC) 1195:13:20, 28 April 2009 (UTC) 1176:02:45, 29 April 2009 (UTC) 1160:06:10, 28 April 2009 (UTC) 1113:23:08, 30 April 2009 (UTC) 1094:17:20, 30 April 2009 (UTC) 1071:17:20, 30 April 2009 (UTC) 1053:16:20, 29 April 2009 (UTC) 1033:23:09, 29 April 2009 (UTC) 996:23:02, 29 April 2009 (UTC) 973:22:23, 29 April 2009 (UTC) 948:21:01, 29 April 2009 (UTC) 933:20:47, 29 April 2009 (UTC) 914:12:26, 29 April 2009 (UTC) 885:Algebra: A Graduate Course 875:A Course in Modern Algebra 867:04:59, 29 April 2009 (UTC) 833:02:45, 29 April 2009 (UTC) 814:17:43, 28 April 2009 (UTC) 733:17:20, 30 April 2009 (UTC) 719:02:45, 29 April 2009 (UTC) 687:06:10, 28 April 2009 (UTC) 669:03:51, 28 April 2009 (UTC) 654:03:08, 28 April 2009 (UTC) 639:01:27, 28 April 2009 (UTC) 624:00:26, 28 April 2009 (UTC) 609:23:58, 27 April 2009 (UTC) 586:23:45, 27 April 2009 (UTC) 558:01:11, 30 April 2009 (UTC) 544:04:42, 29 April 2009 (UTC) 525:02:45, 29 April 2009 (UTC) 495:21:13, 27 April 2009 (UTC) 451:20:40, 27 April 2009 (UTC) 436:20:18, 27 April 2009 (UTC) 406:19:21, 27 April 2009 (UTC) 390:18:17, 27 April 2009 (UTC) 371:06:56, 29 April 2009 (UTC) 334:02:45, 29 April 2009 (UTC) 319:20:40, 27 April 2009 (UTC) 301:20:25, 27 April 2009 (UTC) 286:19:39, 27 April 2009 (UTC) 272:19:21, 27 April 2009 (UTC) 248:18:04, 27 April 2009 (UTC) 224:19:23, 27 April 2009 (UTC) 201:17:43, 27 April 2009 (UTC) 178:17:19, 27 April 2009 (UTC) 157:16:22, 27 April 2009 (UTC) 83:16:22, 27 April 2009 (UTC) 3472:Mathematical applications 2296:, an arbitrary term in a 1785:Mentioned ambiguity of "( 3843:Please do not modify it. 3831:21:48, 10 May 2009 (UTC) 3772:21:48, 10 May 2009 (UTC) 3748:21:48, 10 May 2009 (UTC) 3723:21:48, 10 May 2009 (UTC) 3571:Equivalent matrix method 3560:Equivalent matrix method 3540:01:39, 18 May 2009 (UTC) 3515:01:39, 18 May 2009 (UTC) 3490:14:11, 16 May 2009 (UTC) 3447:16:26, 14 May 2009 (UTC) 3423:16:26, 14 May 2009 (UTC) 3402:16:26, 14 May 2009 (UTC) 3381:16:26, 14 May 2009 (UTC) 3356:16:26, 14 May 2009 (UTC) 3322:23:06, 11 May 2009 (UTC) 3307:06:42, 11 May 2009 (UTC) 3266:14:11, 16 May 2009 (UTC) 3247:16:04, 14 May 2009 (UTC) 3221:06:42, 11 May 2009 (UTC) 3182:06:42, 11 May 2009 (UTC) 3151:23:06, 11 May 2009 (UTC) 3136:06:42, 11 May 2009 (UTC) 3046:Much better, thank you! 3027:16:00, 14 May 2009 (UTC) 3013:03:32, 11 May 2009 (UTC) 2943:15:57, 14 May 2009 (UTC) 2924:03:32, 11 May 2009 (UTC) 2901:04:13, 10 May 2009 (UTC) 2869:03:32, 11 May 2009 (UTC) 2776:03:32, 11 May 2009 (UTC) 2756:04:13, 10 May 2009 (UTC) 1862:15:52, 14 May 2009 (UTC) 36:Please do not modify it. 3811:15:58, 8 May 2009 (UTC) 3762:OK, citation provided. 3692:10:32, 4 May 2009 (UTC) 3673:19:59, 3 May 2009 (UTC) 3110:03:35, 9 May 2009 (UTC) 3081:03:35, 9 May 2009 (UTC) 3056:03:35, 9 May 2009 (UTC) 2998:03:35, 9 May 2009 (UTC) 2972:03:35, 9 May 2009 (UTC) 2854:03:18, 9 May 2009 (UTC) 2829:03:18, 9 May 2009 (UTC) 2803:03:18, 9 May 2009 (UTC) 2734:03:32, 9 May 2009 (UTC) 2714:03:18, 9 May 2009 (UTC) 2676:16:58, 5 May 2009 (UTC) 2608:16:58, 5 May 2009 (UTC) 2583:02:29, 6 May 2009 (UTC) 2569:18:04, 5 May 2009 (UTC) 2550:16:58, 5 May 2009 (UTC) 2522:17:04, 5 May 2009 (UTC) 2499:18:04, 5 May 2009 (UTC) 2483:16:58, 5 May 2009 (UTC) 2455:18:04, 5 May 2009 (UTC) 2440:16:58, 5 May 2009 (UTC) 2415:09:36, 5 May 2009 (UTC) 2386:09:36, 5 May 2009 (UTC) 2328:09:36, 5 May 2009 (UTC) 2280:16:31, 5 May 2009 (UTC) 2264:09:36, 5 May 2009 (UTC) 2221:18:52, 4 May 2009 (UTC) 2205:10:32, 4 May 2009 (UTC) 2183:10:32, 4 May 2009 (UTC) 2162:10:32, 4 May 2009 (UTC) 2135:00:57, 8 May 2009 (UTC) 2120:13:59, 4 May 2009 (UTC) 2105:11:36, 4 May 2009 (UTC) 2090:10:32, 4 May 2009 (UTC) 2068:10:32, 4 May 2009 (UTC) 2054:GCD(462, 1071) = 3×7"? 2043:10:32, 4 May 2009 (UTC) 2006:10:06, 5 May 2009 (UTC) 1991:22:40, 3 May 2009 (UTC) 1932:22:23, 3 May 2009 (UTC) 1917:20:05, 3 May 2009 (UTC) 1900:09:59, 4 May 2009 (UTC) 1848:00:57, 8 May 2009 (UTC) 1825:02:29, 6 May 2009 (UTC) 1803:10:10, 5 May 2009 (UTC) 1768:18:52, 4 May 2009 (UTC) 1753:09:59, 4 May 2009 (UTC) 1714:09:59, 4 May 2009 (UTC) 1650:16:58, 3 May 2009 (UTC) 1630:10:16, 3 May 2009 (UTC) 1606:13:57, 2 May 2009 (UTC) 1506:10:25, 3 May 2009 (UTC) 1487:16:11, 1 May 2009 (UTC) 1132:00:01, 1 May 2009 (UTC) 752:14:54, 8 May 2009 (UTC) 376:Applied to real numbers 3454:It seems odd that the 3431:Historical development 3140:Ah, so much better! -- 2688:Knowledge (XXG) is not 2124:Good enough for me. -- 1398: 1275:mathematical induction 1241:mathematical induction 796: 795:{\displaystyle a=bq+r} 762:Comment on terminology 470:File:Gabriel-Lamé.jpeg 418:. Book X of Euclid's 3554:The closing lines of 2743:explain the algorithm 2403:Fermat's Last Theorem 1393: 895:Undergraduate Algebra 797: 462:Oppose on criterion 3 141:Diophantine equations 2666:. I'll make a link. 1961:prescriptive grammar 1674:Other number systems 959:published by the AMS 898:(2005), and Lowen's 771: 1253:ideal (ring theory) 1143:Conditional Support 1099:The article should 65:Euclidean algorithm 56:21:05, 19 May 2009 3172:OK, Peter it is. 2720:edited mercilessly 2682:I don't think the 2664:modular arithmetic 1698:abstract algebraic 1682:abstract algebraic 1332:Leaning to support 1202:Looking to support 1018:division algorithm 840:division algorithm 821:division algorithm 792: 570:Lack of citations? 478:File:Dedekind.jpeg 424:incommensurability 3759:Citation needed. 3456:Bezout's identity 2882:Eudoxus of Cnidus 2793:OK, sounds good. 2424:proof of validity 1982:Fowler&fowler 1969:16.4 million hits 1702:Euclidean domains 1690:Gaussian integers 1686:Euclidean domains 1472:The animated gif 1207:Fowler&fowler 1147:too comprehensive 1006:Topics in Algebra 964:Fowler&fowler 905:Fowler&fowler 844:Topics in Algebra 842:, but Herstein's 805:Fowler&fowler 234:Oldest algorithm? 132: 131: 86: 3854: 3845: 3231:Euclidean domain 2395:infinite descent 1988: 1983: 1700:notions such as 1684:notions such as 1588:to the power of 1351:Support the lead 1257:infinite descent 1249:infinite descent 1213: 1208: 970: 965: 911: 906: 878:(1989), Rowen's 852:Euclidean domain 811: 806: 801: 799: 798: 793: 145:abstract algebra 104: 71: 48:The article was 38: 3862: 3861: 3857: 3856: 3855: 3853: 3852: 3851: 3850: 3841: 3365:Sturm's theorem 2684:implementations 2657: 2647: 2637: 2557: 2536: 2532: 2371: 2362: 2353: 2343: 2312: 2305: 2294: 2027:imperative mood 1986: 1981: 1597: 1587: 1578: 1569: 1557: 1548: 1539: 1530: 1415:Jakob.scholbach 1280:Jakob.scholbach 1227:Jakob.scholbach 1211: 1206: 1079:Intelligibility 968: 963: 909: 904: 892:(2004), Lang's 882:(1994), Lang's 809: 804: 769: 768: 513:Collected Works 191:development". 68: 34: 22: 21: 20: 12: 11: 5: 3860: 3858: 3849: 3848: 3837: 3836: 3835: 3834: 3833: 3803:131.111.216.15 3800: 3799: 3798: 3797: 3796: 3795: 3792: 3789: 3786: 3778: 3777: 3776: 3775: 3774: 3754: 3753: 3752: 3751: 3750: 3729: 3728: 3727: 3726: 3725: 3699: 3698: 3697: 3696: 3695: 3694: 3660: 3659: 3658: 3657: 3649: 3634: 3583: 3580: 3577: 3574: 3563: 3552: 3549: 3546: 3545: 3544: 3543: 3542: 3521: 3520: 3519: 3518: 3517: 3496: 3495: 3494: 3493: 3492: 3451: 3450: 3449: 3427: 3426: 3425: 3406: 3405: 3404: 3385: 3384: 3383: 3360: 3359: 3358: 3330: 3329: 3328: 3327: 3326: 3325: 3324: 3280: 3279: 3278: 3277: 3276: 3275: 3274: 3273: 3272: 3271: 3270: 3269: 3268: 3202: 3201: 3200: 3199: 3198: 3188: 3187: 3186: 3185: 3184: 3159: 3158: 3157: 3156: 3155: 3154: 3153: 3116: 3115: 3114: 3113: 3112: 3087: 3086: 3085: 3084: 3083: 3062: 3061: 3060: 3059: 3058: 3037: 3036: 3035: 3034: 3033: 3032: 3031: 3030: 3029: 2978: 2977: 2976: 2975: 2974: 2953: 2952: 2951: 2950: 2949: 2948: 2947: 2946: 2945: 2907:anthyphairesis 2877: 2876: 2875: 2874: 2873: 2872: 2871: 2835: 2834: 2833: 2832: 2831: 2809: 2808: 2807: 2806: 2805: 2784: 2783: 2782: 2781: 2780: 2779: 2778: 2738: 2737: 2736: 2698:when I arrived 2680: 2679: 2678: 2652: 2642: 2633: 2626: 2625: 2624: 2623: 2622: 2591: 2590: 2589: 2588: 2587: 2586: 2585: 2555: 2534: 2530: 2526: 2525: 2524: 2505: 2504: 2503: 2502: 2501: 2461: 2460: 2459: 2458: 2457: 2419: 2418: 2417: 2390: 2389: 2388: 2366: 2358: 2348: 2339: 2332: 2331: 2330: 2310: 2303: 2292: 2286: 2285: 2284: 2283: 2282: 2227: 2226: 2225: 2224: 2223: 2187: 2186: 2185: 2166: 2165: 2164: 2145: 2144: 2143: 2142: 2141: 2140: 2139: 2138: 2137: 2072: 2071: 2070: 2047: 2046: 2045: 2018: 2017: 2016: 2015: 2014: 2013: 2012: 2011: 2010: 2009: 2008: 1945: 1874: 1873: 1872: 1871: 1870: 1869: 1868: 1867: 1866: 1865: 1864: 1774: 1773: 1772: 1771: 1770: 1718: 1717: 1716: 1653: 1652: 1635: 1634: 1633: 1632: 1609: 1608: 1592: 1583: 1573: 1565: 1559: 1558: 1553: 1543: 1535: 1525: 1519: 1518: 1511: 1510: 1509: 1508: 1490: 1489: 1466: 1465: 1464: 1463: 1462: 1461: 1460: 1459: 1458: 1457: 1387: 1386: 1385: 1384: 1366: 1365: 1347: 1346: 1328: 1327: 1326: 1325: 1324: 1323: 1322: 1321: 1320: 1319: 1219: 1218: 1198: 1197: 1179: 1178: 1163: 1162: 1139: 1138: 1116: 1115: 1081: 1080: 1076: 1075: 1074: 1073: 1056: 1055: 1040: 1039: 1002:I. N. Herstein 984: 983: 982: 981: 980: 979: 978: 977: 976: 975: 935: 791: 788: 785: 782: 779: 776: 764: 763: 759: 758: 757: 756: 755: 754: 739: 706: 705: 704: 703: 702: 701: 700: 699: 698: 697: 696: 695: 694: 693: 671: 589: 588: 572: 571: 567: 566: 565: 564: 563: 562: 561: 560: 483: 482: 474: 465: 464: 458: 457: 456: 455: 454: 453: 378: 377: 347: 346: 345: 344: 343: 342: 341: 340: 339: 338: 337: 336: 236: 235: 231: 230: 229: 228: 227: 226: 206: 205: 204: 203: 181: 180: 164: 163: 162:Game of Euclid 130: 129: 128: 127: 125:External links 122: 117: 109: 108: 102: 101: 95: 94: 88: 87: 73:Nominator(s): 67: 62: 61: 46: 45: 25: 23: 15: 14: 13: 10: 9: 6: 4: 3: 2: 3859: 3847: 3844: 3838: 3832: 3828: 3824: 3819: 3818: 3817: 3816: 3815: 3814: 3813: 3812: 3808: 3804: 3793: 3790: 3787: 3784: 3783: 3782: 3781: 3779: 3773: 3769: 3765: 3761: 3760: 3758: 3757: 3755: 3749: 3745: 3741: 3736: 3735: 3733: 3732: 3730: 3724: 3720: 3716: 3711: 3710: 3709: 3708: 3706: 3705: 3704: 3703: 3693: 3689: 3685: 3681: 3680: 3679: 3678: 3677: 3676: 3675: 3674: 3671: 3670: 3666: 3654: 3650: 3647: 3643: 3639: 3635: 3632: 3628: 3624: 3620: 3616: 3612: 3608: 3604: 3600: 3596: 3592: 3588: 3584: 3581: 3578: 3575: 3572: 3568: 3564: 3561: 3557: 3553: 3550: 3547: 3541: 3537: 3533: 3529: 3528: 3527: 3526: 3525: 3522: 3516: 3512: 3508: 3504: 3503: 3502: 3501: 3500: 3497: 3491: 3487: 3483: 3479: 3478: 3477: 3476: 3475: 3473: 3469: 3465: 3461: 3457: 3452: 3448: 3444: 3440: 3435: 3434: 3432: 3428: 3424: 3420: 3416: 3412: 3411: 3410: 3407: 3403: 3399: 3395: 3391: 3390: 3389: 3386: 3382: 3378: 3374: 3370: 3369: 3368: 3366: 3361: 3357: 3353: 3349: 3345: 3344: 3343: 3340: 3336: 3331: 3323: 3320: 3319: 3315: 3310: 3309: 3308: 3304: 3300: 3296: 3292: 3288: 3287: 3286: 3285: 3284: 3281: 3267: 3263: 3259: 3254: 3253: 3250: 3249: 3248: 3244: 3240: 3236: 3232: 3228: 3227: 3224: 3223: 3222: 3218: 3214: 3210: 3209: 3208: 3207: 3206: 3203: 3196: 3195: 3194: 3193: 3192: 3189: 3183: 3179: 3175: 3171: 3170: 3169: 3168: 3167: 3165: 3160: 3152: 3149: 3148: 3144: 3139: 3138: 3137: 3133: 3129: 3124: 3123: 3122: 3121: 3120: 3117: 3111: 3107: 3103: 3099: 3098: 3097: 3096: 3095: 3093: 3088: 3082: 3078: 3074: 3070: 3069: 3068: 3067: 3066: 3063: 3057: 3053: 3049: 3045: 3044: 3043: 3042: 3041: 3038: 3028: 3024: 3020: 3016: 3015: 3014: 3011: 3010: 3006: 3001: 3000: 2999: 2995: 2991: 2986: 2985: 2984: 2983: 2982: 2979: 2973: 2969: 2965: 2961: 2960: 2959: 2958: 2957: 2954: 2944: 2940: 2936: 2931: 2927: 2926: 2925: 2922: 2921: 2917: 2912: 2908: 2904: 2903: 2902: 2898: 2894: 2889: 2888: 2887: 2886: 2885: 2883: 2878: 2870: 2867: 2866: 2862: 2857: 2856: 2855: 2851: 2847: 2843: 2842: 2841: 2840: 2839: 2836: 2830: 2826: 2822: 2817: 2816: 2815: 2814: 2813: 2810: 2804: 2800: 2796: 2792: 2791: 2790: 2789: 2788: 2785: 2777: 2774: 2773: 2769: 2764: 2759: 2758: 2757: 2753: 2749: 2744: 2739: 2735: 2732: 2731: 2727: 2721: 2717: 2716: 2715: 2711: 2707: 2703: 2699: 2694: 2693: 2692: 2691: 2689: 2685: 2681: 2677: 2673: 2669: 2665: 2661: 2660: 2659: 2655: 2651: 2645: 2641: 2636: 2632: 2627: 2621: 2620: 2616: 2611: 2610: 2609: 2605: 2601: 2597: 2596: 2595: 2592: 2584: 2580: 2576: 2572: 2571: 2570: 2567: 2566: 2562: 2553: 2552: 2551: 2547: 2543: 2539: 2538: 2537: 2527: 2523: 2519: 2515: 2511: 2510: 2509: 2506: 2500: 2497: 2496: 2492: 2486: 2485: 2484: 2480: 2476: 2471: 2470: 2469: 2467: 2462: 2456: 2453: 2452: 2448: 2443: 2442: 2441: 2437: 2433: 2429: 2428: 2427: 2425: 2420: 2416: 2412: 2408: 2404: 2400: 2399: 2398: 2396: 2391: 2387: 2383: 2379: 2375: 2374: 2373: 2369: 2365: 2361: 2357: 2351: 2347: 2342: 2338: 2333: 2329: 2325: 2321: 2317: 2316: 2315: 2313: 2306: 2299: 2295: 2287: 2281: 2278: 2277: 2273: 2267: 2266: 2265: 2261: 2257: 2253: 2249: 2245: 2241: 2237: 2233: 2232: 2231: 2228: 2222: 2219: 2218: 2214: 2208: 2207: 2206: 2202: 2198: 2193: 2192: 2191: 2188: 2184: 2180: 2176: 2172: 2171: 2170: 2167: 2163: 2159: 2155: 2151: 2150: 2149: 2146: 2136: 2133: 2132: 2128: 2123: 2122: 2121: 2117: 2113: 2108: 2107: 2106: 2102: 2098: 2093: 2092: 2091: 2087: 2083: 2078: 2077: 2076: 2073: 2069: 2065: 2061: 2057: 2056: 2055: 2053: 2048: 2044: 2040: 2036: 2032: 2028: 2024: 2023: 2022: 2019: 2007: 2003: 1999: 1994: 1993: 1992: 1989: 1984: 1978: 1974: 1970: 1966: 1962: 1958: 1954: 1950: 1946: 1943: 1939: 1935: 1934: 1933: 1930: 1929: 1925: 1920: 1919: 1918: 1914: 1910: 1906: 1903: 1902: 1901: 1897: 1893: 1889: 1888: 1886: 1882: 1878: 1875: 1863: 1859: 1855: 1851: 1850: 1849: 1846: 1845: 1841: 1836: 1832: 1828: 1827: 1826: 1822: 1818: 1814: 1813: 1811: 1806: 1805: 1804: 1800: 1796: 1792: 1788: 1784: 1783: 1782: 1780: 1775: 1769: 1766: 1765: 1761: 1756: 1755: 1754: 1750: 1746: 1742: 1741: 1739: 1736: 1732: 1728: 1724: 1719: 1715: 1711: 1707: 1703: 1699: 1695: 1691: 1687: 1683: 1679: 1678: 1677: 1675: 1670: 1669: 1668: 1667: 1663: 1658: 1655: 1654: 1651: 1648: 1644: 1640: 1637: 1636: 1631: 1627: 1623: 1618: 1613: 1612: 1611: 1610: 1607: 1604: 1601: 1595: 1591: 1586: 1582: 1576: 1572: 1568: 1564: 1561: 1560: 1556: 1552: 1546: 1542: 1538: 1534: 1528: 1524: 1521: 1520: 1516: 1513: 1512: 1507: 1503: 1499: 1494: 1493: 1492: 1491: 1488: 1484: 1480: 1475: 1471: 1468: 1467: 1456: 1452: 1448: 1444: 1443: 1442: 1438: 1434: 1430: 1426: 1425: 1424: 1420: 1416: 1412: 1411: 1410: 1406: 1402: 1397: 1391: 1390: 1389: 1388: 1383: 1379: 1375: 1370: 1369: 1368: 1367: 1364: 1360: 1356: 1352: 1349: 1348: 1345: 1341: 1337: 1333: 1330: 1329: 1318: 1314: 1310: 1306: 1305: 1304: 1300: 1296: 1291: 1290: 1289: 1285: 1281: 1276: 1272: 1271: 1270: 1266: 1262: 1258: 1254: 1250: 1246: 1242: 1238: 1237: 1236: 1232: 1228: 1224: 1221: 1220: 1217: 1214: 1209: 1203: 1200: 1199: 1196: 1192: 1188: 1184: 1183:Strong Oppose 1181: 1180: 1177: 1173: 1169: 1165: 1164: 1161: 1157: 1153: 1148: 1144: 1141: 1140: 1136: 1135: 1134: 1133: 1129: 1125: 1121: 1114: 1110: 1106: 1102: 1098: 1097: 1096: 1095: 1091: 1087: 1078: 1077: 1072: 1068: 1064: 1060: 1059: 1058: 1057: 1054: 1050: 1046: 1042: 1041: 1037: 1036: 1035: 1034: 1030: 1026: 1021: 1019: 1015: 1011: 1007: 1003: 998: 997: 993: 989: 974: 971: 966: 960: 956: 951: 950: 949: 945: 941: 936: 934: 930: 926: 921: 917: 916: 915: 912: 907: 901: 897: 896: 891: 887: 886: 881: 877: 876: 870: 869: 868: 864: 860: 856: 853: 849: 845: 841: 836: 835: 834: 830: 826: 822: 818: 817: 816: 815: 812: 807: 789: 786: 783: 780: 777: 774: 761: 760: 753: 749: 745: 740: 736: 735: 734: 730: 726: 722: 721: 720: 716: 712: 708: 707: 690: 689: 688: 684: 680: 676: 672: 670: 666: 662: 657: 656: 655: 651: 647: 642: 641: 640: 636: 632: 627: 626: 625: 621: 617: 612: 611: 610: 606: 602: 598: 593: 592: 591: 590: 587: 583: 579: 574: 573: 569: 568: 559: 555: 551: 547: 546: 545: 541: 537: 533: 528: 527: 526: 522: 518: 514: 510: 506: 501: 500: 499: 498: 497: 496: 492: 488: 481: 479: 475: 473: 471: 467: 466: 463: 460: 459: 452: 448: 444: 439: 438: 437: 433: 429: 425: 421: 417: 416:Dedekind cuts 413: 409: 408: 407: 403: 399: 394: 393: 392: 391: 387: 383: 375: 374: 373: 372: 368: 364: 360: 356: 352: 335: 331: 327: 322: 321: 320: 316: 312: 308: 304: 303: 302: 298: 294: 289: 288: 287: 283: 279: 275: 274: 273: 269: 265: 261: 258: 254: 253: 252: 251: 250: 249: 245: 241: 233: 232: 225: 221: 217: 212: 211: 210: 209: 208: 207: 202: 198: 194: 189: 185: 184: 183: 182: 179: 175: 171: 166: 165: 161: 160: 159: 158: 154: 150: 146: 142: 138: 137:RSA algorithm 126: 123: 121: 118: 116: 113: 112: 111: 110: 105: 100: 97: 93: 90: 85: 84: 80: 76: 70: 69: 66: 63: 60: 58: 55: 51: 44: 42: 37: 32: 27: 26: 19: 3842: 3839: 3801: 3701: 3700: 3663: 3661: 3652: 3645: 3641: 3637: 3630: 3626: 3622: 3618: 3614: 3610: 3606: 3602: 3598: 3594: 3590: 3586: 3570: 3566: 3559: 3555: 3523: 3498: 3471: 3468:Applications 3467: 3464:Applications 3463: 3460:Applications 3459: 3455: 3453: 3430: 3408: 3387: 3362: 3332: 3312: 3294: 3290: 3282: 3204: 3190: 3161: 3141: 3118: 3091: 3089: 3064: 3039: 3003: 2980: 2955: 2929: 2914: 2910: 2906: 2879: 2859: 2837: 2811: 2786: 2766: 2742: 2724: 2719: 2683: 2653: 2649: 2643: 2639: 2634: 2630: 2628: 2613: 2593: 2559: 2528: 2507: 2489: 2465: 2463: 2445: 2423: 2421: 2392: 2367: 2363: 2359: 2355: 2349: 2345: 2340: 2336: 2334: 2308: 2301: 2290: 2288: 2270: 2251: 2247: 2243: 2239: 2235: 2229: 2211: 2189: 2168: 2147: 2125: 2110:reference. 2074: 2051: 2049: 2030: 2020: 1976: 1972: 1960: 1956: 1952: 1948: 1941: 1937: 1922: 1884: 1883:prime number 1880: 1876: 1838: 1834: 1830: 1790: 1786: 1778: 1776: 1758: 1734: 1730: 1726: 1722: 1720: 1673: 1671: 1660: 1656: 1638: 1593: 1589: 1584: 1580: 1574: 1570: 1566: 1562: 1554: 1550: 1544: 1540: 1536: 1532: 1526: 1522: 1514: 1469: 1394: 1350: 1331: 1259:instead. -- 1222: 1201: 1182: 1146: 1142: 1119: 1117: 1100: 1082: 1022: 1013: 1005: 999: 985: 919: 893: 883: 873: 847: 843: 839: 765: 512: 484: 476: 468: 461: 419: 379: 354: 348: 256: 237: 133: 120:Citation bot 72: 49: 47: 35: 28: 3665:Cryptic C62 3335:Sturm chain 3314:Cryptic C62 3143:Cryptic C62 3005:Cryptic C62 2916:Cryptic C62 2861:Cryptic C62 2768:Cryptic C62 2761:you choose 2726:Cryptic C62 2702:seven years 2615:Cryptic C62 2561:Cryptic C62 2491:Cryptic C62 2447:Cryptic C62 2272:Cryptic C62 2213:Cryptic C62 2127:Cryptic C62 1924:Cryptic C62 1905:Neither/nor 1840:Cryptic C62 1760:Cryptic C62 1694:polynomials 1662:Cryptic C62 1579:looks like 1187:Ottava Rima 1122:obscurity. 1120:unnecessary 744:Ottava Rima 646:Ottava Rima 616:Ottava Rima 578:Ottava Rima 188:FA criteria 3339:WP:MOSLINK 2466:Background 1617:accessible 1429:WP:MOSMATH 1010:Serge Lang 767:equation: 257:nontrivial 3565:The term 3342:directly. 3164:Dirichlet 1996:class". 1245:recursion 359:this book 307:algorithm 3823:Proteins 3764:Proteins 3740:Proteins 3715:Proteins 3702:Comments 3684:Proteins 3656:section. 3625:divides 3601:divides 3589:divides 3558:(before 3532:Proteins 3507:Proteins 3482:Proteins 3439:Proteins 3415:Proteins 3394:Proteins 3373:Proteins 3348:Proteins 3299:Proteins 3295:specific 3258:Proteins 3239:Proteins 3213:Proteins 3174:Proteins 3128:Proteins 3102:Proteins 3073:Proteins 3048:Proteins 3019:Proteins 2990:Proteins 2964:Proteins 2935:Proteins 2893:Proteins 2846:Proteins 2821:Proteins 2795:Proteins 2763:WP:UNDUE 2748:Proteins 2706:Proteins 2668:Proteins 2600:Proteins 2575:Proteins 2542:Proteins 2514:Proteins 2475:Proteins 2432:Proteins 2407:Proteins 2378:Proteins 2320:Proteins 2256:Proteins 2246:implies 2238:implies 2197:Proteins 2175:Proteins 2154:Proteins 2112:Proteins 2082:Proteins 2060:Proteins 2035:Proteins 1998:Proteins 1909:Awadewit 1892:Proteins 1854:Proteins 1817:Proteins 1795:Proteins 1745:Proteins 1706:Proteins 1657:Comments 1643:Ealdgyth 1639:Comments 1622:Proteins 1603:Fatuorum 1498:Proteins 1479:Pichpich 1447:Awadewit 1355:Awadewit 1309:Proteins 1168:Proteins 1124:Proteins 1086:Proteins 1063:Proteins 1045:Looie496 957:(2008), 825:Proteins 725:Proteins 711:Proteins 550:Awadewit 517:Proteins 487:Awadewit 428:Proteins 420:Elements 326:Proteins 293:Proteins 193:Proteins 149:Proteins 115:Analysis 75:Proteins 54:Karanacs 50:promoted 3636:"where 3291:general 1810:vectors 1600:Malleus 1515:Support 1223:Support 1152:Lwnf360 1105:Lwnf360 1014:Algebra 920:Algebra 679:Lwnf360 382:El Caro 278:El Caro 240:El Caro 107:Toolbox 3567:matrix 3071:Good! 2930:Topics 2911:Topics 2533:< r 2298:series 1987:«Talk» 1212:«Talk» 1137:!Votes 969:«Talk» 910:«Talk» 810:«Talk» 597:WP:SCG 534:). -- 3235:below 2487:: --> 1659:from 692:(UTC) 412:surds 16:< 3827:talk 3807:talk 3768:talk 3744:talk 3719:talk 3688:talk 3669:Talk 3644:and 3536:talk 3511:talk 3486:talk 3443:talk 3419:talk 3398:talk 3377:talk 3352:talk 3318:Talk 3303:talk 3262:talk 3243:talk 3217:talk 3178:talk 3147:Talk 3132:talk 3106:talk 3077:talk 3052:talk 3023:talk 3009:Talk 2994:talk 2968:talk 2939:talk 2920:Talk 2897:talk 2865:Talk 2850:talk 2825:talk 2799:talk 2772:Talk 2752:talk 2730:Talk 2710:talk 2672:talk 2648:mod 2619:Talk 2604:talk 2579:talk 2565:Talk 2546:talk 2518:talk 2495:Talk 2479:talk 2451:Talk 2436:talk 2411:talk 2382:talk 2324:talk 2276:Talk 2260:talk 2254:=7. 2217:Talk 2201:talk 2179:talk 2158:talk 2152:OK. 2131:Talk 2116:talk 2101:talk 2086:talk 2064:talk 2039:talk 2002:talk 1953:viz. 1928:Talk 1913:talk 1896:talk 1887:" ? 1858:talk 1844:Talk 1833:and 1821:talk 1799:talk 1779:lots 1764:Talk 1749:talk 1733:-by- 1725:and 1710:talk 1692:and 1666:Talk 1647:Talk 1626:talk 1502:talk 1483:talk 1451:talk 1437:talk 1419:talk 1405:talk 1378:talk 1359:talk 1340:talk 1313:talk 1299:talk 1284:talk 1265:talk 1247:and 1231:talk 1191:talk 1172:talk 1156:talk 1128:talk 1109:talk 1090:talk 1067:talk 1049:talk 1029:talk 1008:and 992:talk 944:talk 929:talk 863:talk 829:talk 748:talk 729:talk 715:talk 683:talk 665:talk 650:talk 635:talk 620:talk 605:talk 582:talk 554:talk 540:talk 521:talk 491:talk 447:talk 432:talk 402:talk 386:talk 367:talk 355:best 330:talk 315:talk 297:talk 282:talk 268:talk 244:talk 220:talk 197:talk 186:The 174:talk 153:talk 79:talk 3470:to 2535:k-1 2307:or 2304:n-1 2097:C S 1977:are 1973:are 1955:6) 1949:can 1881:are 1812:." 1704:." 1433:C S 1401:C S 1374:C S 1336:C S 1295:C S 1261:C S 1101:NOT 1025:C S 1012:'s 1004:'s 988:C S 940:C S 925:C S 859:C S 848:the 661:C S 631:C S 601:C S 536:C S 443:C S 398:C S 363:C S 311:C S 264:C S 216:C S 170:C S 168:-- 147:. 52:by 3829:) 3809:) 3770:) 3746:) 3721:) 3690:) 3667:· 3662:-- 3640:, 3633:". 3605:, 3538:) 3513:) 3488:) 3445:) 3421:) 3400:) 3379:) 3354:) 3337:. 3316:· 3305:) 3264:) 3245:) 3219:) 3180:) 3145:· 3134:) 3108:) 3079:) 3054:) 3025:) 3007:· 2996:) 2970:) 2941:) 2918:· 2899:) 2863:· 2852:) 2827:) 2801:) 2770:· 2754:) 2728:· 2712:) 2674:) 2656:−1 2646:−2 2638:≡ 2617:· 2606:) 2581:) 2563:· 2548:) 2520:) 2493:· 2481:) 2449:· 2438:) 2413:) 2384:) 2370:−1 2354:− 2352:−2 2344:= 2326:) 2274:· 2269:-- 2262:) 2215:· 2203:) 2181:) 2160:) 2129:· 2118:) 2103:) 2088:) 2066:) 2041:) 2031:is 2004:) 1957:is 1942:is 1938:is 1926:· 1915:) 1898:) 1860:) 1842:· 1823:) 1801:) 1789:, 1762:· 1751:) 1712:) 1664:· 1645:- 1628:) 1596:−1 1577:−1 1549:+ 1547:−1 1531:= 1529:−2 1504:) 1485:) 1453:) 1439:) 1421:) 1407:) 1380:) 1361:) 1342:) 1315:) 1301:) 1286:) 1267:) 1243:, 1233:) 1193:) 1174:) 1158:) 1130:) 1111:) 1092:) 1069:) 1051:) 1031:) 1020:. 994:) 946:) 931:) 865:) 831:) 750:) 731:) 717:) 685:) 667:) 652:) 637:) 622:) 607:) 584:) 556:) 542:) 523:) 493:) 449:) 434:) 404:) 388:) 369:) 332:) 317:) 299:) 284:) 270:) 246:) 222:) 199:) 176:) 155:) 81:) 59:. 33:. 3825:( 3805:( 3766:( 3742:( 3717:( 3686:( 3646:c 3642:b 3638:a 3631:L 3627:L 3623:p 3619:L 3615:L 3611:L 3607:p 3603:L 3599:p 3595:L 3591:L 3587:p 3573:. 3534:( 3509:( 3484:( 3441:( 3417:( 3396:( 3375:( 3350:( 3301:( 3260:( 3241:( 3215:( 3176:( 3162:" 3130:( 3104:( 3075:( 3050:( 3021:( 2992:( 2966:( 2937:( 2895:( 2848:( 2823:( 2797:( 2750:( 2708:( 2670:( 2654:k 2650:r 2644:k 2640:r 2635:k 2631:r 2629:" 2602:( 2577:( 2556:k 2544:( 2531:k 2516:( 2477:( 2434:( 2409:( 2380:( 2368:k 2364:r 2360:k 2356:q 2350:k 2346:r 2341:k 2337:r 2322:( 2311:0 2309:a 2302:a 2293:n 2291:a 2258:( 2252:n 2248:n 2244:n 2240:n 2236:n 2199:( 2177:( 2156:( 2114:( 2099:( 2084:( 2062:( 2052:n 2037:( 2000:( 1911:( 1894:( 1885:s 1856:( 1835:b 1831:a 1819:( 1797:( 1791:b 1787:a 1747:( 1735:b 1731:a 1727:b 1723:a 1708:( 1624:( 1594:k 1590:r 1585:k 1581:q 1575:k 1571:r 1567:k 1563:q 1555:k 1551:r 1545:k 1541:r 1537:k 1533:q 1527:k 1523:r 1500:( 1481:( 1449:( 1435:( 1417:( 1403:( 1376:( 1357:( 1338:( 1311:( 1297:( 1282:( 1263:( 1229:( 1189:( 1170:( 1154:( 1126:( 1107:( 1088:( 1065:( 1047:( 1027:( 990:( 942:( 927:( 861:( 827:( 790:r 787:+ 784:q 781:b 778:= 775:a 746:( 727:( 713:( 681:( 663:( 648:( 633:( 618:( 603:( 580:( 552:( 538:( 519:( 489:( 445:( 430:( 400:( 384:( 365:( 328:( 313:( 295:( 280:( 266:( 242:( 218:( 195:( 172:( 151:( 77:(

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge (XXG)

:Featured article candidates/Euclidean algorithm/archive1 - Knowledge (XXG)

Index