整除問題（二）

本期主題

證明整除的性質

若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

□