Talk:Division algorithm
From Wikipedia, the free encyclopedia
 |
|||||||||||||||||||||||
| Mathematics rating: | Start Class | Mid Priority | Field: Basics | ||||||||||||||||||||
|
|||||||||||||||||||||||
Contents |
[edit] 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)
[edit] 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
[edit] 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)
[edit] 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.
[edit] 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)
