最大公因数和最小公倍数

最大公因数和最小公倍数封面是BadCen,画师是老福特的太太,大主播当这种文章的封面属实也令我摸不着头脑……上次忘了说参考哪些教材了,复习参考的主要是《整数与多项式》《高等代数简明教程》《华罗庚文集:数论卷Ⅱ》(其实就是数论导引).\textbf{Def.}若a\midb,便称a是b的因数,b是a的倍数.假若a\midb,c,便称a是b,c的公因数;假若a,b\midc,便称c是a,b的公倍数.a,b公因数的最大者称作最大公因数,记作\gcd(a,b);a,b公倍数的最小者称作最小公倍数,记作\text{lcm}(a,b).以上定义容易推广至多个数间.二、理想的交与和对于有理整数环上的理想I_1,I_2,定义I_1\capI_2=\{x\midx\inI_1,I_2\}\\I_1+I_2=\{x_1+x_2\midx_1\inI_1,x_2\inI_2\}\\分别称之为理想的交与和(这定义是容易推广到多个理想且满足结合律的),容易证明理想的交与和仍是理想(验证工作留待读者在某个孤独的情人节深夜进行),那么从上一篇文章对有理整数环上理想的研究,我们知道I_1+I_2,I_1\capI_2将是某个整数生成的理想,这整数与I_1,I_2各自的生成元是否有关?我们先从理想的角度对整除进行一些新的讨论.\textbf{Prop.}a\midb当且仅当(b)\subset(a)(这实际上也可写为b\in(a))\textbf{Prof.}考虑(a)的如下改写:(a)=\{ka\midk\in\mathbb{Z}\}\\于是命题的成立是家喻户晓的.现在再看公约数,我们便知道下面的结论:\textbf{Prop.}(a)\cap(b)=(\text{lcm}(a,b))\\\textbf{Prof.}从上一条命题论述的等价性,我们知道a,b\midc\Leftrightarrowc\in(a)\cap(b),于是(a)\cap(b)便是a,b的倍数的集合,\text{lcm}(a,b)作为这集合的最小元,显然是这理想的生成元,这便是命题所需要的.现在回过头来察看理想的和,采用定义中的符号,令x_2\equiv0,便知道着I_1的所有元素都在I_1+I_2中,也即I_1\subsetI_1+I_2,更进一步的,我们有下面的结论:。\textbf{Prop.}(a)+(b)=(\gcd(a,b))\\\textbf{Prof.}假定(a)+(b)=(d),我们来证明d=\gcd(a,b).一方面,从(a),(b)\subset(d)知道d\mida,b,另外的,对于(d)内的元素k_1a+k_2b及c\mida,b,有c\midk_1a+k_2b\\于是知道(d)\subset(c),也即c\midd,这意味着c\led.于是我们知道d是a,b的因数,且a,b的任意因数都不大于d,这使得d=\gcd(a,b)俨然成立.上面两条重要命题均可较容易地推广之多个理想间.三、GCD与LCM的一些性质\textbf{Prop.}\text{(i)}\gcd(a_1,\cdots,a_n)=\gcd(a_1+k_1a_i,\cdots,a_i,\cdots,a_n+k_na_i)\text{(ii)}\gcd(ma_1,\cdots,ma_n)=m\gcd(a_1,\cdots,a_n)\text{(iii)}\text{lcm}(ma_1,\cdots,ma_n)=m\text{lcm}(a_1,\cdots,a_n)\text{(iv)}a\midb,c,则a\mid\gcd(b,c),b,c\mida,则\text{lcm}(b,c)\mida.\textbf{Prof.}对于(i),应用理想对减法封闭即知道等式两边的数组对应的理想的和是一致的.对于(ii),将等式左边记作D,将等式右边的最大公因数记作d,我们通过证明D,md彼此整除来完成命题的证明.由于\displaystyle(d)=\sum_{i=1}^{n}(a_i),存在a_1,\cdots,a_n的整系数线性组合等于d,也即(这就是鼎鼎有名的\text{Bezout}等式):d=\sum_{i=1}^{n}k_ia_i,k_i\in\mathbb{Z}\\同样的,对于D,我们有D=\sum_{i=1}^{n}k'_ima_i,k'_i\in\mathbb{Z}\\。容易知道d\mida_i,于是md\midma_i,这意味着md是ma_1,\cdots,ma_n的一个公约数,于是显然有md\midD.对于反向的整除式,我们对d的整系数线性表出作如下改写md=\sum_{i=1}^{n}k_ima_i,k_i\in\mathbb{Z}\\等式右边显然在理想\displaystyle\sum_{i=1}^{n}(ma_i)=(D)中,于是D\midmd便是水到渠成的事情了.对于(iii),将等式左边记作L,将等式右边的最大公因数记作l,我们采取与(ii)一致的思路,容易知道a_i\midl,于是ma_i\midml,这意味着ml\in\bigcap_{i=1}^{n}(ma_i)=(L)\\于是L\midml.对于反向的整除式,同样的我们有ma_i\midL,也即\displaystylea_i\midm^{-1}L,于是m^{-1}L\in\bigcap_{i=1}^{n}(a_i)=(l)\\因而l\midm^{-1}L,也即ml\midL.对于(iv),证明第一个等式只需要(a),(b)\subset(c)\Rightarrow(a)+(b)\subset(c)\\而从理想对减法(因而也对加法)封闭来看,这是成立的.对于第二个不等式,这只是下面的断语的简单推论:(c)\subset(a),(b)\Rightarrow(c)\subset(a)\cap(b)\\四、辗转相除法上面证明关于GCD的性质给予了我们一种计算GCD的方法,我们先来证明下面的一条命题:\textbf{Prop.}假定a<b,将有(a,b)=(a,r),其中r=b\moda.\textbf{Prof.}知道b=qa+r,于是(a,b)=(a,qa+r-qa)=(a,r)\\于是为了计算(a,b),我们可以按照如下步骤进行:(a,b)=(a,r_1),r_1=b\moda\\(a,r_1)=(r_1,r_2),r_2=a\modr_1\\\cdots\\直到出现整除,也即(r_i,r_j)=r_i,这r_i便是我们所求的.这计算方法被称为辗转相除法,或\text{Euclid}算法.五、一些习题\textbf{Prob.I}设n是正整数,证明(n!+1,(n+1)!+1)=1\textbf{Prof.}\gcd(n!+1,(n+1)!+1)\\=\gcd(n!+1,n!(n+1)+1)=\gcd(n!+1,n!n)\\=\gcd(n!+1,n!(n-1)-1)=...=\gcd(n!+1,n!(n-i)-i)=...\\=\gcd(n!+1,n!-n+1)=\gcd(n!-n+1,n)。由于n\midn!,n\nmid1-n,(n!+1,(n+1)!+1)=(n!-n+1,n)=1\\\textbf{Prob.II}设m,n为正整数,m为奇数.证明(2^{m}-1,2^{n}+1)=1\textbf{Prof.}由于m为奇数成立,通过因式分解可以证明:2^{n}+1\mid2^{mn}+1\\2^{m}-1\mid2^{mn}-1\\从而有p,q\in\mathbb{Z}使得p(2^{n}+1)=2^{mn}+1,q(2^{m}-1)=2^{mn}-1\\后者也可写作q(2^{m}-1)+2=2^{mn}+1故p(2^{n}+1)=q(2^{m}-1)+2=2^{mn}+1\\。也即p(2^{n}+1)-q(2^{m}-1)=2\\据\text{Bezout}等式这意味着(2^{n}+1,2^{m}-1)\mid2,然而据2^{n}+1,2^{m}-1的奇偶性只能有(2^{n}+1,2^{m}-1)=1\\\textbf{Prob.III}设m,n,a\in\mathbb{N^{+}},证明(a^{m}-1,a^{n}-1)=a^{(m,n)}-1.\textbf{Prof.}不妨设n>m,从而a^{n}-1=a^{m}(a^{n-m}-1)+a^{m}-1\\容易知道a^{m}-1\nmida^{m},故(a^{n}-1,a^{m}-1)=(a^{n-m}-1,a^m-1)\\。重复如上论证将有(a^{n}-1,a^{m}-1)=(a^{n\modm}-1,a^{m}-1)\\再重复如上论证,进行辗转相除有(a^{n}-1,a^{m}-1)=a^{(m,n)}-1\\\textbf{Prob.IV}设a,b是不为0与\pm1的整数,证明存在整数x,y满足ax+by=(a,b)\\。且0\le|x|<|b|,0\le|y|<|a|.\text{Prof.}a=b时显然,其余情况不妨令a<b,据\text{Bezout}等式,ax_{0}+by_{0}=(a,b)\\一定有