PROFILPELAJAR.COM

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 articles
Top	This article has been rated as Top-priority on the project's priority scale.

Numbers

	This article is within the scope of WikiProject Numbers, a collaborative effort to improve the coverage of Numbers 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.NumbersWikipedia:WikiProject NumbersTemplate:WikiProject NumbersNumbers articles
???	This article has not yet received a rating on the project's importance 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 articles
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 GreeceGreek articles
Mid	This article has been rated as Mid-importance on the project's importance scale.

Archives

1, 2, 3, 4

This page has archives. Sections older than 30 days may be automatically archived by when more than 5 sections are present.

__DTSUBSCRIBEBUTTONDESKTOP__{"headingLevel":2,"name":"h-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","type":"heading","level":0,"id":"h-Integers:_ordinary,_normal,_usual,_real,_Gaussian-2018-11-06T11:55:00.000Z","replies":["c-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z-Integers:_ordinary,_normal,_usual,_real,_Gaussian"],"text":"Integers: ordinary, normal, usual, real, Gaussian","linkableTitle":"Integers: ordinary, normal, usual, real, Gaussian"}-->

Integers: ordinary, normal, usual, real, Gaussian

__DTELLIPSISBUTTON__{"threadItem":{"headingLevel":2,"name":"h-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","type":"heading","level":0,"id":"h-Integers:_ordinary,_normal,_usual,_real,_Gaussian-2018-11-06T11:55:00.000Z","replies":["c-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z-Integers:_ordinary,_normal,_usual,_real,_Gaussian"]}}-->

__DTLATESTCOMMENTTHREAD__{"id":"c-Maproom-2018-11-06T14:28:00.000Z-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","timestamp":"2018-11-06T14:28:00.000Z"}__-->__DTCOMMENTCOUNT__3__-->__DTAUTHORCOUNT__3__-->

__DTSUBSCRIBEBUTTONMOBILE__{"headingLevel":2,"name":"h-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","type":"heading","level":0,"id":"h-Integers:_ordinary,_normal,_usual,_real,_Gaussian-2018-11-06T11:55:00.000Z","replies":["c-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z-Integers:_ordinary,_normal,_usual,_real,_Gaussian"],"text":"Integers: ordinary, normal, usual, real, Gaussian","linkableTitle":"Integers: ordinary, normal, usual, real, Gaussian"}-->

In the § Gaussian integers section, we find these expressions:

"ordinary integers"
"normal integers".

I found these terms confusing, since

I don't recall seeing them used, in decades of reading maths, before this; and
The phrase "normal integers" occurs in close proximity to a discussion of a norm.

Perhaps both of the above phrases were meant to specify the usual or everyday integers, namely those in (or isomorphic to those in) the real numbers? In any case, the sense of the section wouldn't suffer, and accuracy would improve, if we were to replace both "ordinary integers" and "normal integers" by "real integers".

Before I make such a change, I'd like to hear other opinions.

yoyo (talk) 11:55, 6 November 2018 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2018-11-06T11:55:00.000Z","author":"Yahya Abdal-Aziz","type":"comment","level":1,"id":"c-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z-Integers:_ordinary,_normal,_usual,_real,_Gaussian","replies":["c-D.Lazard-2018-11-06T12:35:00.000Z-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","c-Maproom-2018-11-06T14:28:00.000Z-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z"],"displayName":"yoyo"}}-->

The phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from algebraic integers. The phrase "normal integer" is less common and must changed into "ordinary integer". "Real integer" is not a good idea, because it would be WP:OR, and also because

{\sqrt {2}}

(for example) is an algebraic integer and a real number. I'll change "normal" to "ordinary", and add an explanatory footnote after the first use of "ordinary". D.Lazard (talk) 12:35, 6 November 2018 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2018-11-06T12:35:00.000Z","author":"D.Lazard","type":"comment","level":2,"id":"c-D.Lazard-2018-11-06T12:35:00.000Z-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","replies":[]}}-->

I agree with D.Lazard. "Ordinary integers" is not at all confusing, "normal integers" may be slightly confusing, but "real integers" is definitely confusing. Maproom (talk) 14:28, 6 November 2018 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2018-11-06T14:28:00.000Z","author":"Maproom","type":"comment","level":2,"id":"c-Maproom-2018-11-06T14:28:00.000Z-Yahya_Abdal-Aziz-2018-11-06T11:55:00.000Z","replies":[]}}-->

__DTSUBSCRIBEBUTTONDESKTOP__{"headingLevel":2,"name":"h-109.149.2.98-2019-04-07T13:49:00.000Z","type":"heading","level":0,"id":"h-Inconsistent_history-2019-04-07T13:49:00.000Z","replies":["c-109.149.2.98-2019-04-07T13:49:00.000Z-Inconsistent_history"],"text":"Inconsistent history","linkableTitle":"Inconsistent history"}-->

Inconsistent history

__DTELLIPSISBUTTON__{"threadItem":{"headingLevel":2,"name":"h-109.149.2.98-2019-04-07T13:49:00.000Z","type":"heading","level":0,"id":"h-Inconsistent_history-2019-04-07T13:49:00.000Z","replies":["c-109.149.2.98-2019-04-07T13:49:00.000Z-Inconsistent_history"]}}-->

__DTLATESTCOMMENTTHREAD__{"id":"c-Wcherowi-2019-04-07T19:02:00.000Z-109.149.2.98-2019-04-07T13:49:00.000Z","timestamp":"2019-04-07T19:02:00.000Z"}__-->__DTCOMMENTCOUNT__2__-->__DTAUTHORCOUNT__2__-->

__DTSUBSCRIBEBUTTONMOBILE__{"headingLevel":2,"name":"h-109.149.2.98-2019-04-07T13:49:00.000Z","type":"heading","level":0,"id":"h-Inconsistent_history-2019-04-07T13:49:00.000Z","replies":["c-109.149.2.98-2019-04-07T13:49:00.000Z-Inconsistent_history"],"text":"Inconsistent history","linkableTitle":"Inconsistent history"}-->

The present text of the article says that the Euclidean algorithm was first described in Europe by Bachet in 1624. This can hardly be true if it was already described in Euclid's Elements, which was known in Europe in various editions and translations long before Bachet.109.149.2.98 (talk) 13:49, 7 April 2019 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2019-04-07T13:49:00.000Z","author":"109.149.2.98","type":"comment","level":1,"id":"c-109.149.2.98-2019-04-07T13:49:00.000Z-Inconsistent_history","replies":["c-Wcherowi-2019-04-07T19:02:00.000Z-109.149.2.98-2019-04-07T13:49:00.000Z"]}}-->

Point well taken. The source only says that Bachet gave the first numerical description of the algorithm in Europe. I'll edit this. --Bill Cherowitzo (talk) 19:02, 7 April 2019 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2019-04-07T19:02:00.000Z","author":"Wcherowi","type":"comment","level":2,"id":"c-Wcherowi-2019-04-07T19:02:00.000Z-109.149.2.98-2019-04-07T13:49:00.000Z","replies":[],"displayName":"Bill Cherowitzo"}}-->

__DTSUBSCRIBEBUTTONDESKTOP__{"headingLevel":2,"name":"h-D.Lazard-2019-06-18T08:47:00.000Z","type":"heading","level":0,"id":"h-Section_\"Non_commutative_rings\"-2019-06-18T08:47:00.000Z","replies":["c-D.Lazard-2019-06-18T08:47:00.000Z-Section_\"Non_commutative_rings\""],"text":"Section \"Non commutative rings\"","linkableTitle":"Section \"Non commutative rings\""}-->

Section "Non commutative rings"

__DTELLIPSISBUTTON__{"threadItem":{"headingLevel":2,"name":"h-D.Lazard-2019-06-18T08:47:00.000Z","type":"heading","level":0,"id":"h-Section_\"Non_commutative_rings\"-2019-06-18T08:47:00.000Z","replies":["c-D.Lazard-2019-06-18T08:47:00.000Z-Section_\"Non_commutative_rings\""]}}-->

__DTLATESTCOMMENTTHREAD__{"id":"c-D.Lazard-2019-06-18T08:47:00.000Z-Section_\"Non_commutative_rings\"","timestamp":"2019-06-18T08:47:00.000Z"}__-->__DTCOMMENTCOUNT__1__-->__DTAUTHORCOUNT__1__-->

__DTSUBSCRIBEBUTTONMOBILE__{"headingLevel":2,"name":"h-D.Lazard-2019-06-18T08:47:00.000Z","type":"heading","level":0,"id":"h-Section_\"Non_commutative_rings\"-2019-06-18T08:47:00.000Z","replies":["c-D.Lazard-2019-06-18T08:47:00.000Z-Section_\"Non_commutative_rings\""],"text":"Section \"Non commutative rings\"","linkableTitle":"Section \"Non commutative rings\""}-->

It seems that the only known example is the ring of Hurwitz quaternions. This must be clarified. If is true, the section must be renamed "Hurwitz quaternions". Otherwise, it must be named "Non commutative Euclidean rings" and moved to Euclidean domain. D.Lazard (talk) 08:47, 18 June 2019 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2019-06-18T08:47:00.000Z","author":"D.Lazard","type":"comment","level":1,"id":"c-D.Lazard-2019-06-18T08:47:00.000Z-Section_\"Non_commutative_rings\"","replies":[]}}-->

__DTSUBSCRIBEBUTTONDESKTOP__{"headingLevel":2,"name":"h-Hexagonalpedia-2021-05-23T12:18:00.000Z","type":"heading","level":0,"id":"h-Inaccurate_implementations-2021-05-23T12:18:00.000Z","replies":["c-Hexagonalpedia-2021-05-23T12:18:00.000Z-Inaccurate_implementations"],"text":"Inaccurate implementations","linkableTitle":"Inaccurate implementations"}-->

Inaccurate implementations

__DTELLIPSISBUTTON__{"threadItem":{"headingLevel":2,"name":"h-Hexagonalpedia-2021-05-23T12:18:00.000Z","type":"heading","level":0,"id":"h-Inaccurate_implementations-2021-05-23T12:18:00.000Z","replies":["c-Hexagonalpedia-2021-05-23T12:18:00.000Z-Inaccurate_implementations"]}}-->

__DTLATESTCOMMENTTHREAD__{"id":"c-D.Lazard-2021-05-24T16:39:00.000Z-Hexagonalpedia-2021-05-23T12:18:00.000Z","timestamp":"2021-05-24T16:39:00.000Z"}__-->__DTCOMMENTCOUNT__2__-->__DTAUTHORCOUNT__2__-->

__DTSUBSCRIBEBUTTONMOBILE__{"headingLevel":2,"name":"h-Hexagonalpedia-2021-05-23T12:18:00.000Z","type":"heading","level":0,"id":"h-Inaccurate_implementations-2021-05-23T12:18:00.000Z","replies":["c-Hexagonalpedia-2021-05-23T12:18:00.000Z-Inaccurate_implementations"],"text":"Inaccurate implementations","linkableTitle":"Inaccurate implementations"}-->

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]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2021-05-23T12:18:00.000Z","author":"Hexagonalpedia","type":"comment","level":1,"id":"c-Hexagonalpedia-2021-05-23T12:18:00.000Z-Inaccurate_implementations","replies":["c-D.Lazard-2021-05-24T16:39:00.000Z-Hexagonalpedia-2021-05-23T12:18:00.000Z"]}}-->

Fixed D.Lazard (talk) 16:39, 24 May 2021 (UTC)[reply]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"2021-05-24T16:39:00.000Z","author":"D.Lazard","type":"comment","level":2,"id":"c-D.Lazard-2021-05-24T16:39:00.000Z-Hexagonalpedia-2021-05-23T12:18:00.000Z","replies":[]}}-->

__DTSUBSCRIBEBUTTONDESKTOP__{"headingLevel":2,"name":"h-Arthur_Baelde-20240905142800","type":"heading","level":0,"id":"h-Flowcharts-20240905142800","replies":["c-Arthur_Baelde-20240905142800-Flowcharts"],"text":"Flowcharts","linkableTitle":"Flowcharts"}-->

Flowcharts

__DTELLIPSISBUTTON__{"threadItem":{"headingLevel":2,"name":"h-Arthur_Baelde-20240905142800","type":"heading","level":0,"id":"h-Flowcharts-20240905142800","replies":["c-Arthur_Baelde-20240905142800-Flowcharts"]}}-->

__DTLATESTCOMMENTTHREAD__{"id":"c-Jacobolus-20240905171600-Arthur_Baelde-20240905142800","timestamp":"20240905171600"}__-->__DTCOMMENTCOUNT__3__-->__DTAUTHORCOUNT__3__-->

__DTSUBSCRIBEBUTTONMOBILE__{"headingLevel":2,"name":"h-Arthur_Baelde-20240905142800","type":"heading","level":0,"id":"h-Flowcharts-20240905142800","replies":["c-Arthur_Baelde-20240905142800-Flowcharts"],"text":"Flowcharts","linkableTitle":"Flowcharts"}-->

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]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"20240905142800","author":"Arthur Baelde","type":"comment","level":1,"id":"c-Arthur_Baelde-20240905142800-Flowcharts","replies":["c-D.Lazard-20240905162600-Arthur_Baelde-20240905142800","c-Jacobolus-20240905171600-Arthur_Baelde-20240905142800"],"displayName":"Arthur\u00a0Baelde"}}-->

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]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"20240905162600","author":"D.Lazard","type":"comment","level":2,"id":"c-D.Lazard-20240905162600-Arthur_Baelde-20240905142800","replies":[]}}-->

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]__DTELLIPSISBUTTON__{"threadItem":{"timestamp":"20240905171600","author":"Jacobolus","type":"comment","level":2,"id":"c-Jacobolus-20240905171600-Arthur_Baelde-20240905142800","replies":[]}}-->