公因數

在數學中，公因數顯示着若干個整數之間的數論關係。如果一個數同時是幾個數的約數，稱這個數為它們的「公因數」；公約數中最大一個的稱為最大公因數。

在數學分析的敘述中，如果n和d都是整數而且存在某個整數c，使得n = cd，就說d是n的一個因數，或說n是d的一個倍數，記作d|n（讀作d整除n）。如果d|a且d|b我們就稱d是a和b的一個公因數。對每一對整數都有一個公因數d，形如d = ax+by，其中x和y都是整數，並且a和b的每一個公因數都能整除這個d。d的絕對值叫做最大公因數，記為 $\gcd(a,b)$ 。