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

## 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 (talkcontribs) 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 rd implies a-qdd. 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 qq' .
Subtracting the two equations yields: d(q' - q) = (r - r' ).
If d > 0 then r' r and r < dd+r' , and so (r-r' ) < d. Similarly, if d < 0 then rr' 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 q1 and r1, both nonnegative, such that a = bq1 + r1, for example q1 = 0 and r1 = a. If r1 < b, we are done. Otherwise q2 = q1 + 1 and r2 = r1 − b satisfy a = bq2 + r2 and 0 < r2 < r1."

As such, there can be the case where r1 or rk = b, which is fine when considering the condition that r1 < b in order to continue, but not when you state that r2 = r1 - b which would further imply that r2 = 0 and then stating 0 < r2 < r1 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 (talkcontribs) 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)