proof of division algorithm for integers
Let integers (). We want to express for some integers with and that such expression is unique.
Consider the numbers
From all these numbers, there has to be a smallest non negative one. Let it be . Since for some ,11For example, if then . we have . And, if then wasn’t the smallest non-negative number on the list, since the previous (equal to ) would also be non-negative. Thus .
So far, we have proved that we can express as for some pair of integers such that . Now we will prove the uniqueness of such expression.
Let and another pair of integers holding and . Suppose . Since is a number on the list, cannot be smaller or equal than and thus . Notice that
so divides which is impossible since . We conclude that . Finally, if then and therefore . This concludes the proof of the uniqueness part.
|Title||proof of division algorithm for integers|
|Date of creation||2013-03-22 13:01:11|
|Last modified on||2013-03-22 13:01:11|
|Last modified by||drini (3)|