整除问题包括什么（整除问题二）

本期主题证明整除的性质，今天小编就来说说关于整除问题包括什么?下面更多详细答案一起来看看吧!

整除问题包括什么

本期主题

证明整除的性质

若x|z, y|z，(x,y)=1， 则x·y|z。

先来回顾带余除法的定义

带余除法 设m是非零整数，n是任意整数，则可以唯一确定整数q和r,

使得

n=m×q r （0≤r＜|m|）

即

n÷m=q……r （0≤r＜|m|）

其中q和r分别称为商和余数。

下面证明带余除法的唯一性（存在性显然）

证明: 存在q、r，使得

n=m×q r （0≤r＜|m|） ①

若存在q1、r1，使得

n=m×q1 r1 （0≤r1＜|m|）②

②-① 可得

0=m×（q-q1） (r-r1)

∴ (r1-r)=m×（q-q1）

∴ |r-r1|=|m|×|q-q1|

由

0≤r＜|m| 0≤r1＜|m|

可得

|r-r1|＜|m|

所以必然有

|q-q1|=0

∴ q=q1

∴ |r-r1|=|m|×|q-q1|=m×0=0

∴ r=r1 □

---

最大公约数 设m，n是两个整数，q称为m，n的最大公约数，若它满足下面两个条件：

（1）q是m，n的约数；

（2）m，n的约数都是q的约数；

最大公约数记为（m, n）。

引理1 若有等式

n=m×q r ①

成立，那么n、m和m、r有相同的公约数。

证明：若p|m，p|r, 由①得，p|n。这就是说m、r的公约数都是n、m的公约数。反过来

若p|n, p|m，则p一定整除它们的组合

r =n-m×q

这就是说p是m、r的公约数。由此可见，如果n、m有一个最大公约数p，那么p也是m、r的最大公约数。 □

引理2 设m，n是任意两个整数，存在最大公约数p使得

p=u·m v·n

其中u、v是整数。

证明：若m，n中有一个为零，譬如n=0。那么m就是最大公约数。

m=1·m 1·0

下面来看一般情况。不妨设n≠0。根据带余除法

n=q1×m r1 （0≤r1＜|m|）

若r1≠0，再根据带余除法

m=q2×r1 r2 （0≤r2＜|r1|）

若r2≠0，再根据带余除法

r1=q3×r2 r3 （0≤r3＜|r2|）

如此辗转相除下去，显然余数越来越小

|r1|>|r2|> ……

因此在有限次之后，必定有余数为零。于是我们有一串等式；

n=q1×m r1

m=q2×r1 r2

……

rs-2=qs×rs-1 rs

rs-1=qs 1×rs 0

rs与0的最大公约数是rs。根据前面的引理，

rs是rs与rs-1的最大公约数，同理，逐步推上去。

rs是m，n的最大公约数。由上面的倒数第二个等式

rs=rs-2-qs×rs-1

再由倒数第三个等式，

rs-1=rs-3-qs-1×rs-2

带入得

rs=（1 qsqs-1）rs-2-qsrs-3

再次逐步带入，再并项得到

rs=u·m v·n □

现在证明

性质 若x|z, y|z，(x,y)=1 则x·y|z。

证明： 由x|z, y|z，可知

z=m·x

z=n·y

(x,y)=1 由引理可知

1=u·x v·y

两边同时乘z

z=z·u·x z·v·y

z=n·y·u·x m·x·v·y

z=n·u·x·y m·v·x·y

z=(n·u m·v)·(x·y)

综上

x·y|z □

,