Talk:Euclidean algorithm

Bibliography

Would there be any objections to moving the "Bibliography" section to a subsection of "References". This is not a major move but there is more than one reason why it would make sense.

• On Wikipedia a bibliography section is normally the first section in the appendices, usually for biographies, or otherwise "Works" per Works or publications.
• A bibliography of sources, along with a references or notes section providing text-source integrity, constitute the citations so are certainly related.
• The number of GA and FA articles that use a separate sourcing "Bibliography" section is small so it becomes an "exception".

This has nothing to do with any article rating but as "approaching" (GA) and attaining the "best articles Wikipedia has to offer" (FA) other articles are often styled accordingly. The use of "Bibliography" sections in more than one place is confusing and this would remove that aspect and show the relationship as we normally would in subsections. Otr500 (talk) 18:53, 24 July 2018 (UTC)

I see no value in complicating a simple structure, comprising two distinct sections:

1. (hundreds of) specific references, each supporting specific parts of the article, in one (References) section; and
2. a list of (more than a dozen) relevant books for further reading in another (Bibliography) section.

Your proposed alternative puts the books of the bibliography under the heading "References", which implies that they each support some specific assertions made in the article. But that's not necessarily so; and it's not the purpose of a bibliography to do that. yoyo (talk) 12:14, 6 November 2018 (UTC)

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

1. I don't recall seeing them used, in decades of reading maths, before this; and
2. 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)

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)

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)

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)

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)

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)

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)

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

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)