Division Algorithm

    The division algorithm allows us to classify a positive integer according to its remainder. For example, every integer is either even or odd (not both); that is, every integer has a remainder of 0 or 1 when divided by 2.  Although not truly an algorithm in the traditional sense, the division algorithm allows us to prove statements about the integers by considering only a finite number of cases.

Proposition (Division Algorithm) If and are integers such that then there are unique integers and such that with The integers and are called the quotient and the remainder in the division of by

    Proof. Consider the set The set is nonempty because since By the Well Ordering Principle has a least positive integer, say Thus, there exists an integer such that and so with It follows that because otherwise, which contradicts the choice of as the least positive integer in
    To prove that and are unique, assume that we have two equations and with and By subtracting the second of the equations from the first we have, Thus divides and since   and we have Thus can divide only if Therefore, and also by the equations involving and Whence the quotient and remainder are unique.   

    One of the advantages of the division algorithm is that it allows us to prove statements about the integers by considering only a finite number of cases.

Example (Division Algorithm) Show that the expression is an integer for any positive integer

    Solution. Equivalently, we need to show that is of the form for some for any positive integer By the division algorithm, has exactly one of the forms or If for some then



is an integer.  If for some then



is an integer. Finally, if is of the form then we have



which is an integer. Therefore, in all cases,   is an integer for any positive integer

Example (Division Algorithm) Show that the product of any three consecutive integers is divisible by

    Solution. Let be an integer. We need to show that is of the form The division algorithm yields that is either even or odd (not both). In either case, must be even. The integer is also divisible by 3, since one of or is of the form Since is even and is divisible by 3, it must be divisible by 6.

Proposition (Division Algorithm - Alternate Form) If and are integers such that then there are unique integers and such that with

    Proof. Suppose we are given integers and If then we have the division algorithm which stated there exists unique and such that with and so in fact we have   with If then the statement is trivially true. The only other case is to assume So we apply the division algorithm with and obtaining unique integers and such that with Let and then with This and is unique for this and because otherwise would contradict the division algorithm.

• print this page
• pages linking here
• related pages

Calculus for Dummies List Price: $19.99 Buy Used: $8.00 You Save: $11.99 (60%) New (59) Used (56) from $8.00 The mere thought of having to take a required calculus course is enough to make legions of students break out in a cold sweat. Others who have no intention of ever studying the subject have this notion (more)

Calculus (With Analytic Geometry)(8th edition) List Price: $198.95 Buy Used: $68.80 You Save: $130.15 (65%) New (46) Used (75) from $68.80 Designed for the three-semester calculus course for math and science majors, Calculus continues to offer instructors and students new and innovative teaching and learning resources. This was the first (more)

Calculus: Early Transcendentals (Stewart's Calculus Series) List Price: $197.95 Buy New: $111.65 You Save: $86.30 (44%) New (32) Used (39) from $111.65 Success in your calculus course starts here! James Stewart's CALCULUS texts are world-wide best-sellers for a reason: they are clear, accurate, and filled with relevant, real-world examples. With CALCULUS: (more)

The Humongous Book of Calculus Problems: For People Who Don't Speak Math List Price: $18.95 Buy New: $11.01 You Save: $7.94 (42%) New (32) Used (17) from $10.00 Now students have nothing to fear ? Math textbooks can be as baffling as the subject they?re teaching. Not anymore. The best-selling author of The Complete Idiot?s Guide to Calculus has taken what appears (more)

TI-89 Graphing Calculator For Dummies (For Dummies (Math & Science)) List Price: $21.99 Buy New: $11.79 You Save: $10.20 (46%) New (32) Used (14) from $11.49 Do you own a TI-89, TI-89 Titanium, TI-92 Plus, or a Voyage 200 graphing calculator? If you do, or if you need to get one for school or your job, then you need to know how it works and how to make the (more)