在解有關最大公約數、最小公倍數的問題時,常用到以下結論: (1)如果兩個自然數是互質數,那麼它們的最大公約數是1,最小公倍數是這兩個數的乘積。 (2)如果兩個自然數中,較大數是較小數的倍數,那麼較小數就是這兩個數的最大公約數,較大數就是這兩個數的最小公倍數。 (3)兩個整數分別除以它們的最大公約數,所得的商是互質數。 (4)兩個自然數的最大公約數與它們的最小公倍數的乘積等於這兩個數的乘積。 (5)GCD(a,b) is the smallest positive linear combination of a and b. a與b的最大公約數是最小的a與b的正線性組合,即對於方程xa+yb=c來說,若x,a,y,b都為整數,那麼c的最小正根為gcd(a,b)。
6和9的最大公因數是3.
擴充套件資料公因數,亦稱“公約數”。它是一個能同時整除若干整數的整數 。如果一個整數同時是幾個整數的因數,稱這個整數為它們的“公因數”;公因數中最大的稱為最大公因數。
給定若干個整數,如果有一個(些)數是它們共同的因數,那麼這個(些)數就叫做它們的公因數。而全部公因數中最大的那個,稱為這些整數的最大公因數。
公約數與公倍數相反,就是既是A的約數同時也是B的約數的數,12和15的公約數有1,3,最大公約數就是3。再舉個例子,30和40,它們的公約數有1,2,5,10,最大公約數是10。
公因數,又稱公約數。在數論的敘述中,如果n和d都是整數,而且存在某個整數c,使得n = cd,就說d是n的一個因數,或說n是d的一個倍數,記作d|n(讀作d整除n)。如果d|a且d|b,我們就稱d是a和b的一個公因數。根據裴蜀定理,對每一對整數a,b,都有一個公因數d,使得d = ax+by,其中x和y是某些整數,並且a和b的每一個公因數都能整除這個d。於是d的絕對值叫做最大公因數。
最大公因數,也稱最大公約數、最大公因子,指兩個或多個整數共有約數中最大的一個。a,b的最大公約數記為(a,b),同樣的,a,b,c的最大公約數記為(a,b,c),多個整數的最大公約數也有同樣的記號。求最大公約數有多種方法,常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數,a,b的最小公倍數記為[a,b]。
在解有關最大公約數、最小公倍數的問題時,常用到以下結論: (1)如果兩個自然數是互質數,那麼它們的最大公約數是1,最小公倍數是這兩個數的乘積。 (2)如果兩個自然數中,較大數是較小數的倍數,那麼較小數就是這兩個數的最大公約數,較大數就是這兩個數的最小公倍數。 (3)兩個整數分別除以它們的最大公約數,所得的商是互質數。 (4)兩個自然數的最大公約數與它們的最小公倍數的乘積等於這兩個數的乘積。 (5)GCD(a,b) is the smallest positive linear combination of a and b. a與b的最大公約數是最小的a與b的正線性組合,即對於方程xa+yb=c來說,若x,a,y,b都為整數,那麼c的最小正根為gcd(a,b)。