
Re: Division Algorithm Proof
Posted:
Aug 16, 1999 3:32 AM


* Randy Ades > Does anyone know a proof of the following algorithm(Division Algorithm): > > Let a and b be integers with b > 0. Then there exist unique integers q > and r with the property that > > a = b*q + r, where r >= 0 and r < b.
Hint: Look at the set
S = {ab*t  ab*t nonnegative and t integer }
Prove S is nonempty. From there take the smallest element of S...
Uniqueness: Assume b*q' + r' = b*q + r, then r'  r = b * (q  q') and r'  r < b, and so on.
 Jon Haugsand Norwegian Computing Center, <mailto://haugsand@nr.no> Pho: +47 22852608 / +47 22852500, Fax: +47 22697660, Pb 114 Blindern, N0314 OSLO, Norway

