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

整除问题包括什么(整除问题二)

整除问题包括什么

本期主题

证明整除的性质

若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。根据前面的引理,

rsrsrs-1的最大公约数,同理,逐步推上去。

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

rs=rs-2-qs×rs-1

再由倒数第三个等式,

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

带入得

rs=1 qsqs-1rs-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

,