请输入您要查询的字词:

 

单词 ProofOfDivisionAlgorithmForIntegers
释义

proof of division algorithm for integers


Let a,b integers (b>0). We want to express a=bq+r for some integers q,r with 0r<b and that such expression is unique.

Consider the numbers

,a-3b,a-2b,a-b,a,a+b,a+2b,a+3b,

From all these numbers, there has to be a smallest non negative one. Let it be r.Since r=a-qb for some q,11For example, if r=a+5b then q=-5. we have a=bq+r. And, if rb then r wasn’t the smallest non-negative number on the list, since the previous (equal to r-b) would also be non-negative. Thus 0r<b.

So far, we have proved that we can express a asbq+r for some pair of integers q,r such that 0r<b. Now we will prove the uniqueness of such expression.

Let q and r another pair of integers holding a=bq+r and 0r<b. Suppose rr. Since r=a-bq is a number on the list, cannot be smaller or equal than r and thus r<r. Notice that

0<r-r=(a-bq)-(a-bq)=b(q-q)

so b divides r-r which is impossible since 0<r-r<b. We conclude that r=r.Finally, if r=r then a-bq=a-bq and therefore q=q. This concludes the proof of the uniqueness part.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 3:13:10