關(guān)于最大公因數(shù)的一個(gè)性質(zhì)及證明

趙云平

（臨滄師范高等?？茖W(xué)校 數(shù)理系,云南 臨滄 677099）

關(guān)于最大公因數(shù)的一個(gè)性質(zhì)及證明

趙云平

（臨滄師范高等?？茖W(xué)校 數(shù)理系,云南 臨滄 677099）

最大公因數(shù)也稱最大公約數(shù)，是兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。本文主要討論兩個(gè)整數(shù)的最大公因數(shù)的性質(zhì)，并給出具體的證明。

最大公因數(shù)；輾轉(zhuǎn)相除法；整除；性質(zhì)

1 預(yù)備知識(shí)

在數(shù)論里，最大公因數(shù)是一個(gè)非常重要的概念。最大公因數(shù)滿足兩條，一是公因數(shù)，二是最大。這個(gè)公因數(shù)到底存不存在呢？實(shí)際上這個(gè)公因數(shù)的存在性是比較容易判斷的，因?yàn)?是任何整數(shù)的約數(shù)，所以公因數(shù)肯定是存在的，至少也有個(gè)1。那最大會(huì)不會(huì)存在呢？比如兩個(gè)整數(shù)都取成0，而0可以被任何非零整數(shù)整除，所以它的公約數(shù)是任何的整數(shù)，要找最大，就找不到了。如果不全為0的話，有這樣明顯的結(jié)論，若a1，a2…，an不全為0，則它們的最大公因數(shù)是存在的。存在的話，關(guān)于最大公因數(shù)還有哪些重要的結(jié)論，這是本文研究的出發(fā)點(diǎn)。首先來回顧一下最大公因數(shù)的概念［1-5］。

定義1：若a1，a2…，an是n（n≥2）個(gè)整數(shù)，整數(shù)d是所有ai的因數(shù)，稱d是a1，a2…，an的公因數(shù)。整數(shù)a1，a2…，an的公因數(shù)中最大的一個(gè)，稱為 a1，a2…，an的最大公因數(shù)，記作a1，a2…，an。

定理1：若a1，a2…，an是任意個(gè)不全為零的整數(shù)，則

也就是說將來在討論最大公因數(shù)的時(shí)候，如果里邊的數(shù)有負(fù)號(hào)，可以把負(fù)號(hào)去掉。

定理3：設(shè)a，b，c是任意三個(gè)不全為0的整數(shù)，且a=bq+c，其中q是非零整數(shù)，則(a，b)=(b，c)。

證明：設(shè)（a，b）=d1，（b，c）=d2，證明這兩個(gè)公因數(shù)相等即要證明d1=d2，只要證明d1≤d2，d2≤d1同時(shí)成立，那么這兩個(gè)公因數(shù)相等。

i）證d1≤d2，由已知（a，b）=d1，則d1a，d1b，又c=a-bq，則d1也能整除a，b的線性組合，所以d1c。由d1b，d1c，推出d1是b，c的公因數(shù)，又因?yàn)椋╞，c）=d2，所以d1≤d2。

ii）證d2≤d1，由已知（b，c）=d2，則d2b，d2c，又a=bq+c，則d2也能整除b，c的線性組合，所以d2a。由d2a，d2b，推出d2是a，b的公因數(shù)，又因?yàn)椋╝，b）=d1，所以d2≤d1。

綜上所述，d1=d2，即(a，b)=（b，c）。

定理3的好處就是在求最大公因數(shù)的時(shí)候，可以將大數(shù)化為小數(shù)來求，如此反復(fù)進(jìn)行下去就是所謂的輾轉(zhuǎn)相除法。

2 最大公因數(shù)的性質(zhì)

下面針對(duì)最大公因數(shù)的一個(gè)性質(zhì)，給出詳細(xì)及不同證明方法。性質(zhì)[2]：設(shè)a,b是任意兩個(gè)不全為零的整數(shù)，則

（i）若m是任一正整數(shù)，則(am,bm)=(a,b)m。

教科書中對(duì)于證明過程已經(jīng)寫得很好了，但是不夠明確。

證明：當(dāng)a,b有一個(gè)為零時(shí)，由定理2，定理顯然成立，下面設(shè)a,b都不為零

（i）證法（一），

由定理1，假定a,b＞0，由輾轉(zhuǎn)相除法，有

由（3）（4），得c1=mc2

在求解最大公因數(shù)過程中，應(yīng)用定理（i）可以簡化計(jì)算。

（ii）由結(jié)論（i），

也就是說，a和b都除以最大公因數(shù)求它們的最大公因數(shù)是互質(zhì)的。

由此就得到處理（a，b）=d的一個(gè)很好的辦法：

如果（a,b）=d，那么a=da1，b=db1，且（a1,b1）=1。

反過來也是對(duì)的，d是a、b的公約數(shù)，若a=da1，b=db1，且（a1，b1）=1 ，那么（a，b)=d。這是處理最大公因數(shù)的一個(gè)非常有用的方法。

3 結(jié)論

本文利用輾轉(zhuǎn)相除法和相互整除的關(guān)系證明了兩個(gè)數(shù)的最大公因數(shù)的性質(zhì)（i），從而比較容易地證明了性質(zhì)（ii），如果是多個(gè)數(shù)的公因數(shù)需要做進(jìn)一步討論。

注釋及參考文獻(xiàn)：

[1]陳全國，劉淼.關(guān)于最大公因數(shù)和最小公倍數(shù)的一點(diǎn)注記[J].牡丹江大學(xué)學(xué)報(bào)，2014（10）：140-141.

[2]閔嗣鶴，嚴(yán)士健.初等數(shù)論（第三版）[M].北京：高等教育出版社，2003.

[3]課程教材研究所.初等數(shù)論[M].北京：人民教育出版社，2006.

[4]胡典順,徐漢文.初等數(shù)論[M].北京：科學(xué)出版社，2010.

[5]潘承洞,潘承彪.初等數(shù)論[M].北京：北京大學(xué)出版社，2002.

One Property of the Greatest Common Factor and Its Proof

ZHAO Yun-ping
(Department of Mathematics and Science,Lincang Teachers’College,Lincang,Yunnan 677099)

The greatest common factor is also called the highest common divisor,which is the highest one of the common divisors of two or more integers.The property of the greatest common factor of two integers will be mainly discussed with its concrete proof.

the greatest common factor;algorithm of division;divisibility;the property

O156.1

A

1673-1891（2015）02-0030-02

2015-05-03

趙云平（1982-），女，云南臨滄人，碩士，講師，研究方向:基礎(chǔ)數(shù)學(xué)數(shù)論應(yīng)用，應(yīng)用數(shù)學(xué)運(yùn)籌學(xué)線性規(guī)劃，數(shù)值代數(shù)。