4.2 最大公因数与最小公倍数
本章目录 · 1 节
本章导读
对不全为0的整数 ,共同的正因子中的最大者称最大公因数,记 ,结果取正。对非零整数 ,最小正公倍数称最小公倍数,记 。例如18与24的正公因子为1、2、3、6,所以最大公因数为6;正公倍数为72、144、216等,所以最小公倍数为72。符号不受输入正负影响;()。
定理4.2.1:(1)若 ,则 ;(2)若 ,则 。前者把 除以最小正公倍数,余数仍为公倍数,小于它的非负余数只能为0;后者可用素因子的最小指数或后面的贝祖等式说明。不能只把“最大公因数”理解为数值最大,而漏掉它被全部公因子整除的性质。
对正整数写出统一素数列表的分解 ,缺失素因子取指数0,则
由每一对指数的最小值加最大值等于两者之和,得到正整数情形 ;非零有符号整数应把右侧改为 。
【例4.2.1】求168与300的最大公因数和最小公倍数。
解:,。逐个素因子取最小指数,得 ;取最大指数,得 。乘积检验 。
定理4.2.2:若 ,则 ,这里两组输入不全为0。证明:整除 的数也整除 ;整除 的数也整除 ,所以两组公因子集合完全相同。
辗转相除法反复把输入换成除数与余数;非负余数严格下降,故有限步后余数为0,最后一个非零余数就是最大公因数。负整数输入可先取绝对值。若初始第二输入已经为0,直接返回第一输入绝对值,不要再执行除以0。
定理4.2.3(贝祖等式):不全为0的整数 存在整数 使 。将最后一个非零余数沿辗转相除过程逐步回代,就能构造这样的系数。扩展欧几里得算法把每个余数同时写为原始 的线性组合,余数更新 时,两组系数按相同线性运算更新,因此最后仍得到正确的原始系数。
【例4.2.2】用辗转相除求168与300的最大公因数,并表示成线性组合。
解:依次有 ,,,,,所以最大公因数为12。回代得到
可取 ;代回计算 ,再次确认。贝祖系数通常不唯一。
定义4.2.1: 时称二者互素;多个整数中任意两者互素时称两两互素。两两互素比“全部数的最大公因数为1”更强,例如6、10、15的整体最大公因数为1,但它们并非两两互素。4与15互素,4、9、11、35两两互素,而9与12不互素。
定理4.2.4: 互素当且仅当存在整数 使 。必要性为贝祖等式;充分性由任何共同正因子都整除左侧,因而整除1,只能为1。
【例4.2.3】若 且 ,证明 。
证明:选整数 使 ,乘 得 。第一项因 而被 整除,第二项因 而被 整除,故二者之和也被 整除。互素不可省略,例如2和4均整除4,但8不整除4。
(例完)
