手工求公因数的方法
两个整数 \(a\) 和 \(b\) 的公因数，是能同时整除二者且没有余数的正整数。下面以 48 和 18 为例，介绍逐步方法。
列出每个数的所有因数。依次检验从 1 到 \(\lfloor\sqrt{n}\rfloor\) 的整数 \(d\)。每当 \(d\) 能整除 \(n\)，就同时记下 \(d\) 和 \(n/d\)。对于 48（\(\sqrt{48}\approx 6.93\)，所以检验 1 到 6）：1×48、2×24、3×16、4×12、6×8，得到 1、2、3、4、6、8、12、16、24、48。对于 18（\(\sqrt{18}\approx 4.24\)，所以检验 1 到 4）：1×18、2×9、3×6，得到 1、2、3、6、9、18。
圈出共有的因数。同时出现在两个列表中的因数是 1、2、3 和 6。
最大的共有因数就是最大公因数。这里的最大公因数（GCF）是 6。
捷径：先求最大公因数
质因数分解：48 = 24 · 3，18 = 2 · 32。每个共有质数取其最低次幂：21 · 31 = 6。
欧几里得算法：反复用较大的数去除以较小的数，并用所得余数替换较大的数，直到余数为 0。最后一个非零余数就是最大公因数。
$$48 = 2 \times 18 + 12$$
$$18 = 1 \times 12 + 6$$
$$12 = 2 \times 6 + 0$$
最后一个非零余数是 6，所以 \(\gcd(48,18) = 6\)。可以用计算器核对：48 和 18 的最大公因数是 6。
由最大公因数生成完整列表
\(a\) 和 \(b\) 的每一个公因数都是它们最大公因数的因数，而最大公因数的每一个因数也都是公因数。因此，一旦知道最大公因数，只需列出它的因数即可。对于最大公因数 6，其因数为 1、2、3 和 6，与第 2 步找到的公因数一致。对于较大的数，这种方法快得多，因为只需分解一个数而不是两个。
如果最大公因数是 1，则这两个数互质，它们唯一的公因数是 1。