Talk:Euclidean algorithm

Euclidean algorithm is a featured article; it (or a previous version of it) has been identified as one of the best articles produced by the Wikipedia community. Even so, if you can update or improve it, please do so.

This article appeared on Wikipedia's Main Page as Today's featured article on June 18, 2009.

Article milestones
Date	Process	Result
April 24, 2009	Peer review	Reviewed
May 19, 2009	Featured article candidate	Promoted
February 7, 2015	Featured article review	Kept

Current status: Featured article

Mathematics Top‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Top	This article has been rated as Top-priority on the project's priority scale.

Classical Greece and Rome Mid‑importance

	This article is within the scope of WikiProject Classical Greece and Rome, a group of contributors interested in Wikipedia's articles on classics. If you would like to join the WikiProject or learn how to contribute, please see our project page. If you need assistance from a classicist, please see our talk page.Classical Greece and RomeWikipedia:WikiProject Classical Greece and RomeTemplate:WikiProject Classical Greece and RomeClassical Greece and Rome
Mid	This article has been rated as Mid-importance on the project's importance scale.

Greece Mid‑importance

	Greece portal This article is within the scope of WikiProject Greece, a collaborative effort to improve the coverage of Greece on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.GreeceWikipedia:WikiProject GreeceTemplate:WikiProject GreeceGreece
Mid	This article has been rated as Mid-importance on the project's importance scale.

Archives

1, 2, 3, 4

This page has archives. Topics inactive for 30 days are automatically archived 1 or more at a time by if there are more than 5.

Inaccurate implementations

Latest comment: 5 years ago2 comments2 people in discussion

I feel the implementations given in the Implementations sections are all inaccurate. For example, gcd(-6, 0) is 6, but the implementations return -6. This is wrong because GCDs are always non-negative. Hexagonalpedia (talk) 12:18, 23 May 2021 (UTC)Reply

Fixed D.Lazard (talk) 16:39, 24 May 2021 (UTC)Reply

Flowcharts

Latest comment: 1 year ago3 comments3 people in discussion

At least one flowchart that represents an Euclidean algorithm could be expected. Now no flowchart in the current article. So here are flowcharts.

As though there is no instruction modulo in computing, neither in Python nor in JavaScript for example, the first algorithm computes a remainder through successive subtractions. The second algorithm uses successive modulo operations — % in Python or in JavaScript —, in order to yield the GCD of two natural numbers. A little more complicated, the third algorith is conceived for the easiest mathematical proof of the existence of this “great” divisor, which is multiple of every common divisor of a given pair of natural numbers. This last algorithm keeps unchanged the common divisors of such a pair at every step, by replacing the greatest integer with the positive difference between the two.

By iterating the subtraction of number

d

,
calculation of

n

modulo

d

for

n

and

d

members of ℕ, when

d

is not zero. Example:
if $n$ = 85 and $d$ = 20, then variable $r$ passes
through the values: 85 ↠ 65 ↠ 45 ↠ 25 ↠ 5,
along four courses of the loop. Therefore,
according to the algorithm, divide 85 by 20
yields the remainder
85 – 4 × 20 = 85 modulo 20 = 5.

Through the successive divisions of the
Euclidean algorithm, calculation of the GCD
of natural numbers

d

and

g.

For example,
if their starting values are 20 and 85, then
dividend, divisor and remainder of the unique
division of the loop are, at every step,
three successive terms of this sequence:
20, 85, 20, 5, 0 (5 being a divisor of 20).
Result: gcd(20, 85) = 5.

Every pair of such a sequence:
{85, 20}, {65, 20}, {45, 20},
and so on, has the same set of
common divisors at every step.
So the “great” divisor, multiple of
every divisor of 85 and 20 in this
example, can be computed simply
through successive subtractions.

About the greatest common divisor of two natural numbers, three flowcharts.

If either given integer is zero, then their greatest common divisor
is the other number, because zero is the only multiple
of every integer, the “greatest” for the divisibility.

These three algorithms could be inserted in introduction just after the text, while the antique diagram,
less comprehensible than a flowchart, could be transfered in section
“Background: greatest common divisor” on the right,
the rectangle being placed on the left.
All captions of this multiple image are
well presented in the first two available font‑sizes.
Arthur Baelde (talk) 14:28, 5 September 2024 (UTC)Reply

Flowcharts were a popular method for describing algorithms whent the main control instruction of programming languages was the "go to". Presently, flowcharts are generally replaced by pseudo-code, which is more concise, easier to understand because of its linear structure, and more powerful (it describes programs that cannot be described with flowcharts). The article Flowchart contains The flowchart became a popular tool for describing computer algorithms, but its popularity decreased in the 1970s, when interactive computer terminals and third-generation programming languages became common tools for computer programming, since algorithms can be expressed more concisely as source code in such languages. Often pseudo-code is used, which uses the common idioms of such languages without strictly adhering to the details of a particular one. Also, flowcharts are not well-suited for new programming techniques such as recursive programming.

Also, the manual of style of Wikipedia MOS:MATH#Algorithms says An article about an algorithm may include pseudocode or in some cases source code in some programming language., and does not mention flowcharts at all. Effectively, there are many Wikipedia articles that contain pseudocode, and very few that contain flowcharts.

Presently, the section § Implementations contains the pseudo-code of three versions of the Euclidean algorithm. The most complicate one consists of 7 short lines, and the third one can definitively not be converted into a flow chart. Also, the second one is a much better implementation than your thirs flowcharts.

So, there is no reason for introducing flowcharts in this article, and, in any case, their place is not in the lead. D.Lazard (talk) 16:26, 5 September 2024 (UTC)Reply

I think it would be okay in principle to have a flowchart somewhere in this article, though an algorithm this simple can also be described as a paragraph or written as pseudocode.

I find these particular flow charts pretty hard to read and visually distracting. The most important feature of flow charts is organizing information spatially so it can be easily visually scanned. –jacobolus (t) 17:16, 5 September 2024 (UTC)Reply

Interactive worked examples

Latest comment: 1 year ago6 comments2 people in discussion

I've noticed that a lot of Wikipedia articles on algorithms have worked examples or sometimes GIF animations showing the algorithm step by step. I was thinking it would be cool if there could be an interactive worked example, where the reader can chose the inputs and then see the algorithm work step-by-step. I decided to have a go at trying to create something like that - see my demo on the right. I was wondering what people think of the idea? Bawolff (talk) 16:42, 14 November 2024 (UTC)Reply

I think this is fantastic. Unfortunately though, it doesn't show some of the numbers on dark mode, and doesn't work at all in the actual article for me. IAWW (talk) 21:08, 7 April 2025 (UTC)Reply

I think i fixed the dark mode issues. Can you describe what's happening for you in the article? Does it not show up at all? Does it show up but the buttons don't work? Bawolff (talk) 04:46, 9 April 2025 (UTC)Reply

@Bawolff Ah yes you have fixed the dark mode issues. Thank you!

When I click the start button in the article it doesn't do anything. Interestingly, it works on Chrome (I just tested it). It only happens on Firefox when on the article itself, and there are no errors in the console. I wouldn't worry about it, maybe it is one of my extensions messing things up. IAWW (talk) 08:15, 9 April 2025 (UTC)Reply

Hmm, i tried on firefox and it seems to work for me. Hopefully its just a conflict with some other user script but i'll try and keep an eye out for anyone reporting a similar issue. Bawolff (talk) 10:27, 9 April 2025 (UTC)Reply

Great, must be something about my browser or scripts. Thanks for the great work! IAWW (talk) 11:22, 9 April 2025 (UTC)Reply

Equivalence of implementations

Latest comment: 6 months ago1 comment1 person in discussion

Giving both iterative and recursive codes in the implementation section will lead many to think they are somehow distinct, when merely converting the recursive tail call to iteration produces exactly the iterative code. — Preceding unsigned comment added by ~2026-30709-3 (talk) 03:46, 15 January 2026 (UTC)Reply

Another clumsy proof

Latest comment: 3 months ago7 comments6 people in discussion

This entire thread appears to be merely a WP:SOAPBOX for off-topic and (it turns out) irrelevant personal attacks from a temporary account hiding behind a VPN. If you want to discuss content, try again without personalizing it. —David Eppstein (talk) 05:43, 12 May 2026 (UTC)Reply

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Let me guess. Lazard wrote the "proof".

1. That the algorithm terminates is part of the proof of validity. The section begins assuming some remainder is zero. Possibly the reason is mentioned elsewhere in the article, but it must be at least recalled in a section called Proof of validity.

2. So many words wasted doing badly presented inductions to get the two divisibility conditions and from them the inequalities. The very last line shows what is needed to write a much shorter and also more clear proof. Just prove that $\gcd(x,y)=\gcd(x-y,y)$ , $\gcd(x,0)=x$ for $x\neq$ , and potentially $\gcd(x,y)=\gcd(y,x)$ .~2026-27374-44 (talk) 08:56, 6 May 2026 (UTC)Reply

3. There is no need to introduce the name $g$ when there is already the name $\gcd(a,b)$ for the same entity.

4. The passage from divisibility to inequalities to then get equality is a clunky unnecessary approach. Take into account that the algorithm does not need a notion of order (other than divisibility and a notion of remainders getting smaller) to work. This should be an indication that introducing inequalities is something wasteful. In fact, just from the properties of divisibility, the sets of common divisors of the pairs, $x,y$ and $x-y,y$ are the same. In particular, the greatest common divisors are the same. ~2026-27900-38 (talk) 23:52, 7 May 2026 (UTC)Reply

This kind of rude tone has absolutely no place on Wikipedia talk pages. Please retract or revise your comment, and don't ever write such uncivil comments again in the future. For what it's worth, this material was added in 2009 by User:Proteins (now user:WillowW). –jacobolus (t) 22:32, 9 May 2026 (UTC)Reply

My guess was based on the "proof" in the article about the Extended Euclidean Algorithm, that had the same quality as the proof that was here, and he did write, and on knowing the quality of his writing in general. Which adjectives are appropriate to use in Wikipedia, in this case, that are not considered rude but are accurate? Please, re-write the note accordingly. ~2026-27876-20 (talk) 03:49, 12 May 2026 (UTC)Reply

When you lead with sarcastic personalization, and then go on to call the contribution "clumsy", "clunky", "badly presented", you are just going out of your way to be rude. Please don't do that here. If you just completely removed all of the insults, it would make your point clearer, a lot less distracting, and people would be more likely to take you seriously. You can also skip the scare quotes around "'proof'", which come across as extremely sarcastic/dismissive. Your second comment about "knowing the quality of his writing in general" is also entirely inappropriate. Daniel Lazard's first language is French, and his user page makes it clear that he considers himself to have an "intermediate" level of English fluency. (Personally I think that's too modest, and his English is much better than my French which I would consider "intermediate".) Have you ever tried writing professionally in a second language? –jacobolus (t) 04:52, 12 May 2026 (UTC)Reply

It is the quality of the mathematics, not English or grammar, to which I was referring in every case that I expressed an evaluation. ~2026-28732-75 (talk) 05:19, 12 May 2026 (UTC)Reply

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.