前代数：从算术到代数
最大公因数
假设你有 12 块红瓷砖和 18 块蓝瓷砖，想把它们铺成大小相同的正方形区块，且一块不剩。能整除这两个数目的最大区块边长是 6。这个数——能不留余数地整除每个给定数的最大整数——就是最大公因数。
一种可靠的求法：列出每个数的因数，挑出它们共有的最大者。12 的因数是 1、2、3、4、6、12；18 的因数是 1、2、3、6、9、18；它们共有的最大者是 6。对较大的数，更快的办法是用质因数分解，把它们共有的质因数相乘。
最大公因数是把分数化为最简、以及从代数式中提取公因式的引擎。如果两个数除了 1 没有其他公因数，它们的最大公因数就是 1，称为互素；8 与 15 就是一例。
求 24 与 36 的最大公因数。质因数：24 = 2^3 × 3，36 = 2^2 × 3^2。公共部分：2^2 × 3 = 12。故最大公因数为 12。
对每个共有质数取其最低次幂，再相乘得到最大公因数。
对大数而言，列因数很慢；欧几里得算法通过反复相除迅速求出最大公因数，完全不需要知道任何质因数分解。
又称
另见