带余除法的证明

编程基础 • 2024-12-17 13:27 • 阅读 27

首先先说一下整除的概念

整除：设a , b是两个整数，且b！=0 .如果存在整数 c ,使得 a = b * c,则称a被b整除，或 b 整除 a ，记做 b|a

接下来就是带余除法的定义及其证明:

带余除法：设a , b是两个整数,且b != 0,则存在唯一的整数 q , r (0 <= r < |b|),使得

a = q * b + r , (0 <= r < |b|)

证明带余除法：

—————————————————————————————————————————————

1. 我们首先要证明 0<= r <b:

设集合 S 是a - b * k 组成的所有整数，其中 k 为整数，即s={a - b * k | k ∈ Z} .设T是S中所有非负整数组成

得集合。

则T是非空的（因为当k等于由（小于a / b的集合中）的整数时，b * k < a, 所以此时a - b * k>0,所以T非

空）。所以易得T中得最小素 r = a - b * q(此处的r , q与带余除法中得意义一样)。且r >= 0(因为T是非

负集合) 且r < b(我们可以用反证法来证明 r < b,如果r >= b ,则 r > r - b >= 0,则r - b=a - b * (q+1)

>= 0,所以此时r-b是T中得最小素，这一推论与r是T中最小素相悖）

所以 a = b * q + r, ( 0 <= r < b);

2 .接下来我们要证明q 和 r 是惟一的:

我们假定有两个方程 a = b * q₁ +r₁和 a = b * q₂ + r₂,(0 <= r₁< b,0 <= r₂ < b);两式相减得

r₂ - r₁ =b * (q₁ - q₂)

其中q != 0,所以 b 整除r₂ - r₁，即 b|( r₂- r₁)。

又0 <= r₁< b,0<= r₂<b，所以-b < r₂- r₁ < b.所以结合 b|( r₂ - r₁), r₂ - r₁只能等于0，所以r₂== r₁.

又因为b * q₁+ r₁ == b * q₂ + r₂,所以q₂==q₁;

所以 q 和 r 是惟一的。

以上我们可以得到对于两个整数a,b,当b!=0时，存在惟一的整数q , r(0 <= r <b),使得

a=q * b +r (0 <= r <b);

证毕

今天的文章带余除法的证明分享到此就结束了，感谢您的阅读。