Talk:Euclidean division

Hooshmand?

I'm thinking this stuff doesn't even belong here. It seems more like Hooshmand's own attempt at increasing notoriety for what appear to be publications in fairly obscure or non-peer reviewed journals. —Preceding unsigned comment added by 67.114.158.146 (talk) 10:26, 12 December 2009 (UTC)

Algorithm vs. Theorem

Although the "Division Algorithm" is a theorem, it is so called because of its algorithmic nature. In fact, you can prove it using an algorithm: if you build a q and a r, such that a = q * b + r , then the existence part is proved.

Other question: how do you use the division algorithm to find the GCD of two integers? I know Euclid's Theorem, but it is different, right? joaoferreira

The title say Algorithm, while the article is proving a property about the natural numbers. Thue 21:41, 25 May 2004 (UTC)

Yes, it's a misnomer. I've noted this in the article. — Matt 11:54, 28 May 2004 (UTC)

The major edit was me. I was logged on so long, it logged me out. Oh, well. Revolver 04:18, 13 Jul 2004 (UTC)

Shouldn't this page be called "Division theorem" and search strings for "division algorithm" would be redirected here, since it's been stated that it's not an algorithm, but a theorem? — brithans 16:32, 2008/10/25 —Preceding undated comment was added at 20:33, 25 October 2008 (UTC).

Nice Chandra Kumar Maurya (talk) 07:28, 1 April 2017 (UTC)

Uniqueness?

So, what is unique about Division Algorithm? I would really like to know this because I'm taking Mini University Courses at the University of Ottawa, and I would like to know more about the subject that I'm learning

Uniqueness has a defined meaning in mathematics. It's not the theorem that is unique, rather the numbers that it states exist are unique (in that there aren't any different numbers that do the same thing.) The theorem states that for every two numbers the integers q and r (quotient and remainder) with the properties that it talks about exist. It also says that they are unique because they're the only numbers with those properties (for the two numbers a and d that you happened to be working with.) I thought that was clear from the article but you do have to understand some basic mathematical terms I guess. Or were you really asking why the theorem itself is different from other theorems? --85.64.35.231 (talk) 17:50, 30 October 2009 (UTC)

S is nonempty

"We claim that S contains at least one nonnegative integer . . .."

But we haven't proved that S is nonempty!

---

S contains one element for every integer n. Notice that $an-d$ is in S unconditionally. Jaswenso 00:24, 3 September 2007 (UTC)

assumptions?

Is the division algorithm assuming d<=a ? —Preceding unsigned comment added by 220.227.207.194 (talk) 07:31, 14 September 2007 (UTC)

note am specifically referring to the uniqueness condition. if q=0 then proving uniqueness may not be so easy.. —Preceding unsigned comment added by 220.227.207.194 (talk) 06:16, 17 September 2007 (UTC)

Take this statement: If d > 0 then r' ≤ r and r < d ≤ d+r' , and so (r-r' ) < d. Similarly, if d < 0 then r ≤ r' and r' < -d ≤ -d+r, and so -(r- r' ) < -d. Combining these yields |r- r' | < |d|.

against this example:

5=-1.10+15

5=-2.10+25

q=-2 r=25

q'=-1 r'=15

in the above example d>a, and r<d is not satisfied note that a=qd+r is still satisfied. if we put q=0 we have 0<=r<d ; r=a this also means that given a=qd+r ; if d>a : r= (a-qd) has r=a as the only possible solution. so the statement that q=0, or this bit of the proof has to be added into the main article... I have a specific reason for this as i feel this article is misquoted elsewhere.

misquoted elsewhere?

I am specifically confused as to how the division algorithm helps prove Bézout's_identity

Bézout's_identity states that It states that if a and b are nonzero integers with greatest common divisor d, then there exist integers x and y (called Bézout numbers or Bézout coefficients) such that ax+by=d

It starts by assuming that say a positive "d" exists because ax+by has to be something and that set will have a minimum positive value. It does not assume any value of "d" , it d>a, d<a d=a are all possible values. So "a minimum positive value of d" exists it uses the WLOG with the division algorithm and goes on to show that a=qd+r exists , so r = a − qd = a − q*(ax + by) = a(1 − qx) + b(−qy). this is of the form r=aX+bY it then says "because we have already assumed d is the minimum number that can exist, this r so found has to be zero" else r<d exists, contradicting our assumption that d is the least

Now if d>a q=0 => r=a in the above. So this is now of the form r=aX+bY , with X=1 and Y=0 (i.e. r=a can only be true for one value-pair of X,Y ) So d>a cannot have a possible general solution to the Bezout's Identity. so we can safely assume d<=a? likewise d<=b ? The moment we assume d<=a and d<=b; and because d has to be positive, a and b are positive. We do not need the division algorithm to prove the Bezout's identity because eitherways because given any 2 positive integers (a,b) *note I said any 2 positive integers*, the only value which d can take is d<=a ; d<=b and because d=ax+by , d either has to be divisible by common factors of a and b so d is gcd(a,b) or d is 1 as 1 is the only number less than any 2 random coprime integers. —Preceding unsigned comment added by 122.167.219.198 (talk) 16:34, 24 February 2008 (UTC)

Or this "Bezour identity" can very easily be derived using Dirichlet Approximation Theorem —Preceding unsigned comment added by 128.226.195.71 (talk) 01:22, 17 April 2008 (UTC)

Name as a misnomer

Shouldn't this page be called "Division theorem" and search strings for "division algorithm" would be redirected here, since it's been stated that it's not an algorithm, but a theorem? —Preceding unsigned comment added by Brithans (talk • contribs) 20:30, 25 October 2008 (UTC)

I agree wholeheartedly. I would go beyond that and claim that the "right" form of the theorem should be that for any integer a and positive integer b there exist unique integers q and r satisfying a = bq + r and 0 ≤ r < b. Furthermore the appropriate organization of this material should be not as an article in its own right but rather as part of a (presently nonexistent) article on integer division. Currently division (mathematics) glosses over the crucial difference between real and integer division, which are distinct (though related) operations. Ideally there would separate articles on real and integer division, with the relevant dab page listing them on separate lines. --Vaughan Pratt (talk) 06:47, 1 December 2009 (UTC) (the Pentium floating point division bug guy)

Symbolic representation

Is there anything wrong with this symbolic representation of the division algorithm? I do not plan on posting it in the actual article; I just made it for fun :-)

${a{\in }{\mathbf {Z} }\land d{\in }{\mathbf {Z} }\land d{\neq }{0}\Rightarrow \exists (q{\in }{\mathbf {Z} }\land r{\in }{\mathbf {Z} })({\frac {a}{d}}{=}{q}{+}{\frac {r}{d}}\land r{\geq }{0}\land r{<}{|d|})\land \neg \exists (q{'}{\in }{\mathbf {Z} }\land r{'}{\in }{\mathbf {Z} })({\frac {a}{d}}{=}{q}{'}{+}{\frac {r'}{d}}\land r{'}{\geq }{0}\land r{'}{<}{|d|}\land (q{'}{\neq }{q}\lor r{'}{\neq }{r}))}\!$
JamesMazur22 (talk) 22:25, 22 January 2010 (UTC)

The generalized division algorithm

In the article, it's said in the section (The generalized division algorithm) that

"He states the following theorem in the papers and gives two different proofs for it"

I can't help wondering who is "He". Could the one who wrote this section improve it by giving a reference? —Preceding unsigned comment added by 79.91.213.63 (talk) 13:03, 9 September 2010 (UTC)

Rational arithmetic uses integer arithmetic

Since a recent edit tried to make the article affirm the opposite, let me explain here why one cannot base an integer division algorithm on rational arithmetic, such as computing an exact rational quotient and then rounding down to an integer. Exact rational arithmetic represents fractions as a pair of integers, and if one wants to work with irreducible fractions, this means that common factors from numerator and denominator have to be determined by Euclid's algorithm, which is based on integer division with remainder, and dividing out the gcd found (if greater than 1) also involves the division algorithm. But even if one would never reduce fractions, then still the operation of rounding down to an integer involves exactly the integer division algorithm. So it is not an option to use rational arithmetic to define the division algorithm, the result would be a recursive self-reference without foundation. Marc van Leeuwen (talk) 14:32, 4 March 2011 (UTC)

Why a proof by induction is better

Two times in rapid succession, Lascola replaced a proof by induction by one based on the well ordering principle of the natural numbers, the second time with an edit summary "Could you correct the wrong statement, instead of replacing the whole section?" (never mind that this reintroduces inconsistent naming of variables that I had just somewhat laboriously eliminated). So I guess we should discuss this here on the talk page. For reference, I copy the proof by well-ordering here:

Proof

The proof consists of two parts — first, the proof of the existence of q and r, and second, the proof of the uniqueness of q and r.

Existence

Consider the set

$S=\left\{a-nd:n\in \mathbb {Z} \right\}.$

We claim that S contains at least one nonnegative integer. There are two cases to consider.

• If a is nonnegative, then choose n = 0.
• If a is negative, then choose n = ad.

In both cases, a - nd is nonnegative, and thus S always contains at least one nonnegative integer. This means we can apply the well-ordering principle, and deduce that S contains a least nonnegative integer r. By definition, r = a - nd for some n. Let q be this n. Then, by rearranging the equation, a = qd + r.

It only remains to show that 0 ≤ r < |d|. The first inequality holds because of the choice of r as a nonnegative integer. To show the last (strict) inequality, suppose that r ≥ |d|. Since d ≠ 0, r > 0, and again d > 0 or d < 0.

• If d > 0, then r ≥ d implies a-qd ≥ d. This implies that a-qd-d ≥0, further implying that a-(q+1)d ≥ 0. Therefore, a-(q+1)d is in S and, since a-(q+1)d=r-d with d>0 we know a-(q+1)d<r, contradicting the assumption that r was the least nonnegative element of S.

• If d<0 then r ≥ -d implies that a-qd ≥ -d. This implies that a-qd+d ≥0, further implying that a-(q-1)d ≥ 0. Therefore, a-(q-1)d is in S and, since a-(q-1)d=r+d with d<0 we know a-(q-1)d<r, contradicting the assumption that r was the least nonnegative element of S.

In either case, we have shown that r > 0 was not really the least nonnegative integer in S, after all. This is a contradiction, and so we must have r < |d|. This completes the proof of the existence of q and r.

Uniqueness

Suppose there exists q, q' , r, r' with 0 ≤ r, r' < |d| such that a = dq + r and a = dq' + r' . Without loss of generality we may assume that q ≤ q' .

Subtracting the two equations yields: d(q' - q) = (r - r' ).

If d > 0 then r' ≤ r and r < d ≤ d+r' , and so (r-r' ) < d. Similarly, if d < 0 then r ≤ r' and r' < -d ≤ -d+r, and so -(r- r' ) < -d. Combining these yields |r- r' | < |d|.

The original equation implies that |d| divides |r- r' |; therefore either |d| ≤ |r- 'r' | or |r- r' |=0. Because we just established that |r-r' | < |d|, by trichotomy we may conclude that the first possibility cannot hold. Thus, r=r' .

Substituting this into the original two equations quickly yields dq = dq' and, since we assumed d is not 0, it must be the case that q = q' proving uniqueness.

This proof is basically correct (if one takes d = b), although it could certainly be simplified a bit (for instance by reducing right away to the case b>0, which is easy). But my main difficulty is that this article is called "Division algorithm", so that it should discuss the effectiveness of determining quotient and remainder (the section called Effectiveness does this by referring to the proof, which was indeed correct at the time of writing; just removing the effectiveness claim as suggested by the cited edit summary is not a solution). And the proof above is not effective, because it applies the well ordering principle to an infinite set: even with an algorithm that enumerates elements of such a set there is no effective way of finding a minimal element (you never know if a smaller element will not come along later). Of course this general objection does not prevent finding a minimal element in this concrete example, basically because once you have a non-negative element of S, the only other candidates for a minimal non-negative element of S are those obtained from it by repeatedly subtracting |b| from it, and since all of those are certainly in S, the last one of those which is non-negative (and which will be encountered in finitely many steps) fits the bill. But this is basically what the proof by induction establishes, so why not give such a proof in the first place? As a second remark, I think that more people (among those who are interested in formal proofs) are acquainted with proofs by induction than with proofs using the well-ordering principle, but that is a very minor argument. Marc van Leeuwen (talk) 10:42, 9 March 2011 (UTC)

Name of the article

Several previous posts quote that this article is about a theorem while its title is about an algorithm. As, when mathematicians want to distinguish this division from the usual one, they call it Euclidean division, I'll rename the article in this way. D.Lazard (talk) 11:20, 16 May 2012 (UTC)

Existence Proof Remainder

I was just reading the proof of existence section and where you stated: "Let q₁ and r₁, both nonnegative, such that a = bq₁ + r₁, for example q₁ = 0 and r₁ = a. If r₁ < b, we are done. Otherwise q₂ = q₁ + 1 and r₂ = r₁ − b satisfy a = bq₂ + r₂ and 0 < r₂ < r₁."

As such, there can be the case where r₁ or r_k = b, which is fine when considering the condition that r₁ < b in order to continue, but not when you state that r₂ = r₁ - b which would further imply that r₂ = 0 and then stating 0 < r₂ < r₁ would be incorrect as this would mean that 0 < 0.

Also apologies if I have overlooked or misunderstood anything as I am still fairly new to reading/comprehending proofs. — Preceding unsigned comment added by LausDaeus (talk • contribs) 01:27, 24 September 2012 (UTC)

Good point. Everywhere in the section, 0<r and 0<r' should be read 0≤r and 0≤r'. I have corrected this. D.Lazard (talk) 09:19, 24 September 2012 (UTC)

Well-ordering proof removed??

Well, where did the well-ordering proof go? This is the standard proof presented in just about every math textbook, for good reason: it's clear, succinct, and elegant. There used to be a clunky, tedious proof by induction here, thankfully that is gone, but now there is a proof by "infinite descent". The claim is made that this is a "better" proof because (a) it is constructive, and (b) it avoids well-ordering.

While the proof is constructive, it is also about the worst possible constructive algorithm. And actually, it doesn't avoid well-ordering at all. Consider the line:

Repeating this process one gets eventually q = q_k and r = r_k such that a = bq + r and 0 ≤ r < b.

This is stated as if it were obvious. BUT WHY IS THIS TRUE?

Answer: We have produced a strictly decreasing sequence {r_k} of integers, the first of which is a natural number. This sequence cannot consist entirely of natural numbers, because then we would have a strictly decreasing sequence of natural numbers, which is a contradiction because of... D'OH! ... the well-ordering principle! I guess then, you're supposed to note that at least one of the remainders in the sequence is negative, and use well-ordering AGAIN to find the least such index with negative remainder, then choose the previous remainder as the desired remainder, and then finally prove both parts of the inequality. Whoa... proofs sure look elegant when you leave out half the details, huh?

Here's a good paper explaining why this is hand-waving, unless you use well-ordering: http://www.math.hawaii.edu/~lee/courses/Division.pdf

If you insist on keeping this as the proof given, at least don't try to pretend it doesn't use well-ordering. — Preceding unsigned comment added by 174.50.129.169 (talk) 23:46, 21 March 2015 (UTC)

The example with the negative dividend

"−9 = 4 × (−3) + 3, so −9 divided by 4 is −3 with remainder 3."

This, apart from being unintuitive, contradicts the "0 ≤ r < |b|" condition below ( 3 !< |−3| ). But if changed to "−9 = 4 × (−2) + (−1)", it's no better ( 0 !≤ (−1) ).

Any good sources for this one? 176.221.124.207 (talk) 14:40, 26 March 2016 (UTC)

Here, the divisor b is 4 and the remainder r is 3. That is the quotient q that is −3. We have thus 0 ≤ r < |b|, that is 0 ≤ 3 < 4, and the condition satisfied. D.Lazard (talk) 15:35, 26 March 2016 (UTC)

Euclid's division lemma

Ankiitt‎ has moved, without previous discussion, this article to "Euclid's division lemma". This has been revert by me and others. The first reason for refusing this move is that "Euclidean division" is a common name, while "Euclid's division lemma is not.

Another reason is that the use of "Euclid's" implies that the lemma was known to Euclid, which is, at least unclear. As far as I know (but I am not expert in history), Euclidean division is named after Euclid, because it is the basis of modern versions of Euclidean algorithm. I use the term "modern" because Euclid's version of Euclidean algorithm does not use of division. Therefore the term "Euclid's division lemma" seems completely wrong.

This is for this reason that I have not restored the edit of Michael Hardy asserting that this is named after Euclid: As written, it was somehow misleading. D.Lazard (talk) 09:48, 24 September 2016 (UTC)

If Euclid didn't know it, then it should be stated that it is named after Euclid even though it originated elsewhere. Michael Hardy (talk) 21:50, 24 September 2016 (UTC)

I agree, but saying that it is named after Euclid, without saying that it originated elsewhere is misleading. I do not know any sources for the history of Euclidean division. Thus I am unable to write anything that is not controversial (I am not enough sure of the fact to write in WP that it originated elsewhere). D.Lazard (talk) 09:45, 25 September 2016 (UTC)

I have added an history section, tagged as {{unreferenced section}}. Be free for correcting (if needed) and expanding its content. I have also quoted in Talk:Division (mathematics) the lack of history section in this vital article. D.Lazard (talk) 14:52, 25 September 2016 (UTC)

Euclidean division of polynomials

Euclidean division of polynomials is not considered in this article (except as an example of a Euclidean domain). Therefore, I have added a dab hatnote for linking to Euclidean division of polynomials, which is a section of Polynomial greatest common divisor. It would probably be better to move (and expand) here this section, but I have not the time to be bold and do this now. Also some other advices would be useful. D.Lazard (talk) 12:15, 29 March 2019 (UTC)

Arabic Number System

"In fact, the long division algorithm requires this notation." does not seem quite right. In fact, you can do long division on hours, minutes and seconds. — Preceding unsigned comment added by Chris2crawford (talk • contribs) 07:15, 12 January 2020 (UTC)

Please, open new threads at the bottom of talk pages

Representation of time by hours, minutes and seconds is a variant ot the Hindu–arabic numeral system. However you are right, as some notable (and widely used) division algorithms are independent from any numeral system. I have thus fixed (by changing "requires" into "is based on") and expanded the paragraph. D.Lazard (talk) 08:27, 12 January 2020 (UTC)

Is uniqueness a "main property"?

The article currently states:

• Its main property is that the quotient and the remainder exist and are unique, under some conditions.

Considering only integers, uniqueness may look like an important feature; but as the article states in the section In Euclidean domains, this doesn't generalize; it's a rather specific feature of the integers and only obtains if we require the remainder to be positive, which appears artificial from the point of view of general Euclidean domains (which generally don't have a concept of positivity), and the essential properties of the integers as a Euclidean domain (unique factorization, Bézout identity, existence of greatest common divisors, ...) don't depend on this.

I would suggest to either remove uniqueness in this statement; or, if people think that uniqueness is important for the integers and should be mentioned here, then at least there should be some differentiation in importance between the "main property" that generalizes and the uniqueness that doesn't. If you think that uniqueness is important and should be mentioned here, please say why. Joriki (talk) 08:10, 4 May 2020 (UTC)

I agree that "main" is too strong, since uniqueness is not more important than other properties. I have thus replaced it by "fundamental". Uniqueness is fundamental, because, otherwise, division with remainder would not be well defined. Also many basic tools of number theory depend on the uniqueness, such as the uniqueness of Chinese remainder theorem and the foundation of modular arithmetic (that is, the modulo operation commutes with other arithmetic operations). Also, this is because of the uniqueness that the strong similarity between integers and univariate polynomials does not extend further to other Euclidean domains. D.Lazard (talk) 09:15, 4 May 2020 (UTC)

"Division algorithm for integers" listed at Redirects for discussion

A discussion is taking place to address the redirect Division algorithm for integers. The discussion will occur at Wikipedia:Redirects for discussion/Log/2020 June 9#Division algorithm for integers until a consensus is reached, and readers of this page are welcome to contribute to the discussion. 1234qwer1234qwer4 (talk) 22:58, 9 June 2020 (UTC)

Some important results based on Euclid's division lemma

When a positive integer is divided by 2, the remainder is either 0 or 1. So, any positive integer is of the form 2m, or 2m+1 for some integer m. When any positive integer is divided by 3, the remainder is 0 or 1 or 2. So, any positive integer is of the form 3m, 3m+1, 3m+2 for some integer m. When a positive integer is divided by 4, the remainder can be 0 or 1 or 2 or 3. So, any positive integer is of the form 4m, 4m+1, 4m+2, or 4m+3 for some integer m.

please add these important results based on Euclid's division lemma — Preceding unsigned comment added by Huzaifa abedeen (talk • contribs) 03:37, 1 October 2020 (UTC)

This is not a result that needs to be added. This is simply the special case of Euclid's division lemma with a divisor up to 4 and a quotient denoted by m instead of q. D.Lazard (talk) 07:51, 1 October 2020 (UTC)

Euclidean division by zero?

File:Gcd exercise.gif

Gcd exercise

In case I'm not asking this question in the right place, I'll be asking this same question at Talk:Division by zero.

I'm curious why Euclidean division by zero is never discussed?

It seems like such a simple thing to assume that any dividend divided by zero yields a zero quotient plus a remainder equal to the dividend so that the multiplicative inverse is also true, that: the zero quotient times the zero divisor yields zero plus the remainder yields the original dividend. This may seem useless, yet it is not. For, it is useful to postulate division by zero as modulo zero when GCD factoring using a potentially limitless expansion of the GCD in two-dimensional format. -- Vinyasi (talk) 12:22, 5 January 2023 (UTC)

A very complicate way for saying: Write the largest number on the right of the smallest. Then repeat "(replace the number on the right by the remainder of its division by the number on the left, and exchange the two numbers)" until getting zero. Your division by zero adds nothing but complication.

For teaching to kids, it is even simpler to write the numbers on a row, and at each step to add (on the right of the row) the remainder of the division of the last but one number by the last one. This allows computing the long divisions on the same sheet of paper, if one writes the divisor at the right of the dividend, instead of (usually) at the left. D.Lazard (talk)

File:GCD-for-infinite-sets htm.pdf

JavaScript code of the GCD algorithm for unlimited inputs.

File:GCD Demonstration for Infinite Sets of Integers in Tablature Format driven by PHP.pdf

Screenshot of a GCD Demonstration for an unlimited number of Integers in Tablature Format driven by PHP.

That's a simple example of what it is capable of doing by infinite extension of unlimited number of inputs rather than taking the GCD among each combinatorial pairing. This is not intended for grade school children. This is intended for mathematicians to make their job easier. Sorry if I wasn't clear. -- Vinyasi (talk) 19:53, 5 January 2023 (UTC)

Now that my entries stored on Wikimedia Commons has been removed, here are links to the original copies…

• GCD exercise
• The Expanded Euclidean Algorithm in PHP

Vinyasi (talk) 19:26, 3 October 2023 (UTC)

Flaw in proof

There is a gap in the proof when reducing to the case of positive a. I clarified and made bold the missing step, but for now I'll~have to leave to someone else to figure out the best way to fix it. ––St.nerol (talk) 15:52, 3 October 2023 (UTC)

Good catch. I have fixed the point, and, by the way, rewritten the section for making reading easier (I hope). D.Lazard (talk) 10:59, 4 October 2023 (UTC)

@D.Lazard: Thanks! I changed the start of the second section to say what I think you meant. St.nerol (talk) 19:14, 5 October 2023 (UTC)

Are you sure about having the punctuation inside the online math? The commas look jarring to me. Donald Knuth and people at TeX Stack Exchange seem to seem to agree that they belong outside logically and typographically. –St.nerol (talk) 18:53, 6 October 2023 (UTC)

The need of putting the punctuation before </math> results of a bug in the Wikipedia engine, and is explained in MOS:MATH#PUNC. D.Lazard (talk) 19:02, 6 October 2023 (UTC)