初等数论：最大公因数：\((a,b)\) 最小公倍数：\([a,b]\)

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

一、最大公因数的定义

设\(a\)、\(b\)是两个整数，不全为\(0\)，如果整数\(d\)满足\(d\mid a\)且\(d\mid b\)，那么\(d\)称为\(a\)、\(b\)的公因数。

\(a\)、\(b\)的所有公因数中最大的一个，称为\(a\)、\(b\)的最大公因数，记作\(\gcd(a,b)\)或\((a,b)\)。

规定：\((0,0)=0\)

例如，\(12\)和\(18\)，它们的公因数有\(1\)、\(2\)、\(3\)、\(6\)，所以\((12,18)=6\)。

例如，因为\(2\mid 0\)、\(2\mid 2\)，所以\((0,2)=(2,0)=2\)

二、求最大公因数的方法

列举法：分别列出两个数的所有因数，然后找出它们的公因数中最大的那个。

例如，求\((8,12)\)

\(8\)的因数有\(1\)、\(2\)、\(4\)、\(8\)

\(12\)的因数有\(1\)、\(2\)、\(3\)、\(4\)、\(6\)、\(12\)

它们的公因数是\(1\)、\(2\)、\(4\)，所以\((8,12)=4\)。

辗转相除法（欧几里得算法）：设\(a\)、\(b\)是两个整数，且\(a > b\)，用\(a\)除以\(b\)得到商\(q\)和余数\(r\)，即\(a = bq + r\)，\(0\leq r < b\)，则\((a,b)=(b,r)\)。不断重复这个过程，直到余数为\(0\)，此时的除数就是最大公因数。

例如，求\((24,18)\)，\(24 = 18\times1 + 6\)，\(18 = 6\times3 + 0\)，所以\((24,18)=6\)。

三、最大公因数的性质

1、定义性：对于两个整数\(a\)、\(b\)（不全为\(0\)），最大公因数\(d = (a,b)\)是满足\(d\mid a\)且\(d\mid b\)的最大整数。

例如，对于\(12\)和\(18\)，公因数有\(1\)、\(2\)、\(3\)、\(6\)，所以\((12,18)=6\)。

2、非负性：\((a,b)\geq1\)，当且仅当\(a = b = 0\)时，规定\((0,0)=0\)；非零整数的最大公因数一定是大于等于\(1\)的整数。

3、交换律：\((a,b)=(b,a)\)。这是因为\(a\)和\(b\)的公因数集合是相同的，与它们的顺序无关。例如，\((7,9)=(9,7)=1\)。

4、结合律：\((a,(b,c))=((a,b),c)\)。

证明如下：

设\(d_1=(a,(b,c))\)，则\(d_1\mid a\)且\(d_1\mid(b,c)\)，所以\(d_1\mid b\)且\(d_1\mid c\)，这说明\(d_1\)是\(a\)、\(b\)、\(c\)的公因数。

设\(d_2=((a,b),c)\)，同理可得\(d_2\)是\(a\)、\(b\)、\(c\)的公因数。

因为\(d_1\)和\(d_2\)都是\(a\)、\(b\)、\(c\)的公因数中的最大值，所以\(d_1 = d_2\)。

例如，对于\(a = 12\)，\(b = 18\)，\(c = 24\)，\((12,(18,24))=(12,6)=6\)，\(((12,18),24)=(6,24)=6\)。

5、分配律：\((ma,mb)=m(a,b)\)（\(m\neq0\)）。证明如下：

设\(d=(a,b)\)，则\(a = dk_1\)，\(b = dk_2\)（\(k_1\)、\(k_2\)为整数），所以\(ma = mdk_1\)，\(mb = mdk_2\)，即\(m(a,b)\mid ma\)且\(m(a,b)\mid mb\)。

设\(e=(ma,mb)\)，则\(ma = e l_1\)，\(mb = e l_2\)（\(l_1\)、\(l_2\)为整数），所以\(a=\frac{e}{m}l_1\)，\(b=\frac{e}{m}l_2\)，因为\(a\)、\(b\)为整数，所以\(m\mid e\)，设\(e = md'\)，则\(d'\mid a\)且\(d'\mid b\)，所以\(d'\leq d\)，又因为\(m(a,b)\mid e\)，所以\(e = m(a,b)\)。

例如，\(m = 3\)，\(a = 4\)，\(b = 6\)，\((3\times4,3\times6)=3(4,6)=3\times2 = 6\)。

6、若\(a\mid b\)，则\((a,b)=a\)：因为\(a\)是\(b\)的因数，所以\(a\)是\(a\)和\(b\)的公因数，且任何其他公因数\(d\)满足\(d\leq a\)，所以\((a,b)=a\)。

例如，若\(5\mid 10\)，则\((5,10)=5\)。

7、若\(d = (a,b)\)，则存在整数\(x\)、\(y\)使得\(ax + by = d\)（裴蜀定理）：这个定理的证明可以通过扩展欧几里得算法得到。

例如，对于\(a = 3\)，\(b = 5\)，\((3,5)=1\)，可以找到\(x = 2\)，\(y=-1\)，使得\(3\times2+5\times(-1)=1\)。

8、多个数的最大公因数：对于\(n\)个整数\(a_1,a_2,\cdots,a_n\)，可以通过两两求最大公因数的方式来计算，如\((a_1,a_2,\cdots,a_n)=(a_1,(a_2,\cdots,a_n))\)，这是结合律的推广。

9、分数的最大公因数：若\(\frac{a}{b}\)和\(\frac{c}{d}\)是两个有理数（\(a\)、\(b\)、\(c\)、\(d\)为整数，\(b\neq0\)，\(d\neq0\)），

定义\((\frac{a}{b},\frac{c}{d})=\frac{(a,c)}{[b,d]}=\frac{子正}{母反}\)（其中\([b,d]\)是最小公倍数），不过这种定义在实际应用中相对较少，主要还是在整数范围内讨论最大公因数的性质。

四、最大公因数的应用场景

化简分数：在分数\(\frac{a}{b}\)中，分子分母同时除以它们的最大公因数，就可以将分数化为最简分数。

例如，对于分数\(\frac{12}{18}\)，\((12,18)=6\)，将分子分母同时除以\(6\)，得到最简分数\(\frac{2}{3}\)。

求解不定方程：对于不定方程\(ax + by = c\)，判断其是否有整数解与\((a,b)\)有关。若\((a,b)\mid c\)，则方程有整数解，并且可以利用扩展欧几里得算法求出解。

例如，对于方程\(3x + 6y = 9\)，\((3,6)=3\)，\(3\mid9\)，所以方程有整数解。

在同余方程中的应用：在数论中，同余方程\(ax\equiv b\pmod{m}\)的求解也会涉及最大公因数。如果\((a,m)\mid b\)，那么同余方程有解。

例如，同余方程\(4x\equiv8\pmod{12}\)，\((4,12)=4\)，\(4\mid8\)，所以该同余方程有解。

五、分数的最大公因数

1. 分数的最大公因数的定义

对于两个分数\(\frac{a}{b}\)和\(\frac{c}{d}\)（\(a,b,c,d\)为整数，\(b\neq0\)，\(d\neq0\)），它们的最大公因数定义为\(\frac{\gcd(a,c)}{\text{lcm}(b,d)}\)，其中\(\gcd(a,c)\)是\(a\)和\(c\)的最大公因数，\(\text{lcm}(b,d)\)是\(b\)和\(d\)的最小公倍数。

例如，对于分数\(\frac{4}{6}\)和\(\frac{8}{10}\)，\(\gcd(4,8) = 4\)，\(\text{lcm}(6,10)=30\)，所以它们的最大公因数是\(\frac{4}{30}=\frac{2}{15}\)。

2. 分数的最大公因数的求法步骤

步骤一：求分子的最大公因数：分别找出两个分数分子的最大公因数。例如，对于\(\frac{12}{15}\)和\(\frac{18}{20}\)，先求\(12\)和\(18\)的最大公因数，通过辗转相除法或者列举因数法可得\(\gcd(12,18)=6\)。

步骤二：求分母的最小公倍数：求出两个分数分母的最小公倍数。对于\(15\)和\(20\)，可以用分解质因数法，\(15 = 3\times5\)，\(20 = 2\times2\times5\)，最小公倍数为\(2\times2\times3\times5 = 60\)。

步骤三：计算分数的最大公因数：将分子的最大公因数作为新分子，分母的最小公倍数作为新分母，得到分数的最大公因数，即\(\frac{6}{60}=\frac{1}{10}\)。

3. 分数的最大公因数的性质

与整数最大公因数的联系：当两个分数的分母都为\(1\)时，分数的最大公因数就退化为整数的最大公因数。

例如，对于\(\frac{a}{1}\)和\(\frac{b}{1}\)，其最大公因数就是\(\gcd(a,b)\)。

约分性质：如果两个分数的最大公因数是\(\frac{e}{f}\)，那么将这两个分数分别除以这个最大公因数，就可以得到最简分数形式（或者相对最简形式）。

例如，对于\(\frac{8}{12}\)和\(\frac{10}{15}\)，它们的最大公因数是\(\frac{2}{3}\)，\(\frac{8}{12}\div\frac{2}{3}=\frac{8\div2}{12\div3}=\frac{4}{4}=1\)，\(\frac{10}{15}\div\frac{2}{3}=\frac{10\div2}{15\div3}=\frac{5}{5}=1\)（这里得到的\(1\)是因为这两个分数本身是成比例的，在一般情况下会得到最简分数）。

乘法性质：若有分数\(\frac{a}{b}\)、\(\frac{c}{d}\)，它们的最大公因数为\(\frac{e}{f}\)，则\((\frac{a}{b}\times\frac{f}{e})\)和\((\frac{c}{d}\times\frac{f}{e})\)的最大公因数为\(1\)。

例如，对于\(\frac{4}{6}\)和\(\frac{8}{10}\)，最大公因数是\(\frac{2}{15}\)，\(\frac{4}{6}\times\frac{15}{2}=5\)，\(\frac{8}{10}\times\frac{15}{2}=6\)，\(\gcd(5,6)=1\)。

一、最小公倍数的定义

对于两个整数\(a\)、\(b\)，它们的最小公倍数\([a,b]\)是指能同时被\(a\)、\(b\)整除的最小正整数。

例如，\([4,6]=12\)，因为\(12\)是既能被\(4\)整除又能被\(6\)整除的最小正整数，\(4\)的倍数有\(4\)、\(8\)、\(12\)、\(16\cdots\)，\(6\)的倍数有\(6\)、\(12\)、\(18\cdots\)。

二、求最小公倍数的方法

1、列举倍数法

分别列出\(a\)、\(b\)的倍数序列，然后从中找出最小的公共倍数。例如求\([6,8]\)：

\(6\)的倍数：\(6\)、\(12\)、\(18\)、\(24\)、\(30\cdots\)

\(8\)的倍数：\(8\)、\(16\)、\(24\)、\(32\cdots\)

所以\([6,8]=24\)。但这种方法对于较大的数效率较低。

2、分解质因数法

将\(a\)、\(b\)分别分解质因数，写成标准的质因数乘积形式，如

\(a = p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\)，\(b = q_1^{l_1}q_2^{l_2}\cdots q_n^{l_n}\)（\(p_i\)、\(q_j\)为质数，\(k_i\)、\(l_j\)为正整数）。

最小公倍数就是取所有出现过的质因数，并取它们在\(a\)、\(b\)中次数较高的那一个对应的次数相乘。

例如，求\([12,18]\)：

\(12 = 2^2\times3\)

\(18 = 2\times3^2\)

质因数有\(2\)和\(3\)，\(2\)的次数在\(12\)中较高为\(2\)次，\(3\)的次数在\(18\)中较高为\(2\)次，所以\([12,18]=2^2\times3^2 = 36\)。

3、利用最大公因数求法

先求出\(a\)、\(b\)的最大公因数\((a,b)\)，再根据公式\([a,b]=\frac{ab}{(a,b)}\)来计算最小公倍数。

例如，已知\((24,36)=12\)，则\([24,36]=\frac{24\times36}{12}=72\)。

三、最小公倍数的性质

1、最小性：若干个整数公有的倍数称为它们的公倍数，其中最小的正整数倍数就是最小公倍数。

例如，\(4\)和\(6\)的公倍数有\(12\)、\(24\)、\(36\)等，其中\(12\)是最小公倍数.

2、非零性：参与求最小公倍数的整数不能全为\(0\)，因为\(0\)乘以任何数都为\(0\)，若包含\(0\)，则不存在最小公倍数.

3、乘积关系：对于任意两个整数\(a\)、\(b\)，它们的最大公因数与最小公倍数的乘积等于\(a\)和\(b\)的乘积，即

\([a,b]\times(a,b)=a\times b\)

例如，\(6\)和\(8\)，\((6,8)=2\)，\([6,8]=24\)，\(2\times24 = 6\times8 = 48\).

4、已知最大公因数求最小公倍数：若已知两个数\(a\)、\(b\)的最大公因数为\(d\)，则它们的最小公倍数为\(\frac{ab}{d}\).

5、互质的两数：如果两个整数\(a\)和\(b\)互质，即\((a,b)=1\)，那么它们的最小公倍数为\(a\times b\) 。

例如，\(3\)和\(5\)互质，它们的最小公倍数就是\(3\times5 = 15\).

6、多个互质数：若\(a_1,a_2,\cdots,a_n\)两两互质，则\([a_1,a_2,\cdots,a_n]=a_1\times a_2\times\cdots\times a_n\) 。

7、可交换性：最小公倍数具有可交换性，即\([a,b]=[b,a]\)。因为最小公倍数是由这两个数的公有质因数和各自独有的质因数相乘得到的，与数的顺序无关.

8、结合律：对于三个整数\(a\)、\(b\)、\(c\)，\([[a,b],c]=[a,[b,c]]\) 。

例如，对于\(2\)、\(3\)、\(4\)，\([[2,3],4]=[6,4]=12\)，\([2,[3,4]]=[2,12]=12\) 。

9、分配律：若\(a\)、\(b\)、\(c\)是整数，且\(a\)是\(b\)和\(c\)的公因数，则\([a,b\times c]=[a,b]\times[a,c]\div a\) 。

10、公倍数是最小公倍数的倍数：\(a\)、\(b\)的任一公倍数必是其最小公倍数\([a,b]\)的倍数。

例如，\(4\)和\(6\)的最小公倍数是\(12\)，它们的其他公倍数\(24\)、\(36\)等都是\(12\)的倍数.

11、分解质因数法计算：先把这几个数分解质因数，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。

例如，求\(12\)和\(18\)的最小公倍数，\(12 = 2^2\times3\)，\(18 = 2\times3^2\)，则最小公倍数为\(2^2\times3^2 = 36\).

12、逐步求法：求多个数的最小公倍数时，可以先求出其中两个数的最小公倍数，再求这个最小公倍数与第三个数的最小公倍数，依次求下去，直到最后一个为止。

例如，求\(4\)、\(6\)、\(8\)的最小公倍数，先求\([4,6]=12\)，再求\([12,8]=24\)，所以\(4\)、\(6\)、\(8\)的最小公倍数是\(24\).

四、最小公倍数的应用场景

分数加减法：在计算异分母分数加减法时，需要先通分，通分的过程就是求分母的最小公倍数。

例如，计算\(\frac{1}{3}+\frac{1}{4}\)，\(\text{lcm}(3,4)=12\)，通分后变为\(\frac{4}{12}+\frac{3}{12}=\frac{7}{12}\)。

周期性问题：在一些具有周期性的问题中，如两个物体分别以不同的周期运动，求它们再次相遇的时间间隔，就需要用到最小公倍数。

例如，一个信号灯每隔\(3\)秒亮一次，另一个信号灯每隔\(4\)秒亮一次，它们同时亮后，下一次同时亮的时间间隔就是\(\text{lcm}(3,4)=12\)秒。

整数分组问题：将一定数量的整数按照两种不同的分组方式进行分组，要使分组后的组数相同，就需要找到两种分组数的最小公倍数。

例如，有一批书，按每\(5\)本一组分或者每\(6\)本一组分，要使两种分法的组数相同，最少需要\(\text{lcm}(5,6)=30\)本书。

五、分数的最小公倍数

1. 分数的最小公倍数定义

对于两个分数\(\frac{a}{b}\)和\(\frac{c}{d}\)（\(a,b,c,d\)为整数，\(b\neq0\)，\(d\neq0\)），它们的最小公倍数定义为\(\frac{\text{lcm}(a,c)}{\gcd(b,d)}\)，这里\(\text{lcm}(a,c)\)表示\(a\)与\(c\)的最小公倍数，\(\gcd(b,d)\)表示\(b\)与\(d\)的最大公因数。

例如，对于分数\(\frac{2}{3}\)和\(\frac{4}{5}\)，\(a = 2\)，\(c = 4\)，\(\text{lcm}(2,4) = 4\)；\(b = 3\)，\(d = 5\)，\(\gcd(3,5) = 1\)，所以它们的最小公倍数是\(\frac{4}{1} = 4\)。

2. 求法分数的最小公倍数步骤

步骤一：求分子的最小公倍数：运用合适的方法（如分解质因数法、列举倍数法等）求出两个分数分子的最小公倍数。比如对于\(\frac{3}{4}\)和\(\frac{6}{8}\)，先求\(3\)和\(6\)的最小公倍数，通过列举倍数可得\(3\)的倍数有\(3,6,9,\cdots\)，\(6\)的倍数有\(6,12,\cdots\)，所以\(\text{lcm}(3,6) = 6\)。

步骤二：求分母的最大公因数：求出两个分数分母的最大公因数。对于\(4\)和\(8\)，利用辗转相除法或者列举因数法可知\(\gcd(4,8) = 4\)。

步骤三：计算分数的最小公倍数：将分子的最小公倍数作为新分子，分母的最大公因数作为新分母，得到分数的最小公倍数，即对于\(\frac{3}{4}\)和\(\frac{6}{8}\)，其最小公倍数为\(\frac{6}{4}=\frac{3}{2}\)。

3. 分数的最小公倍数性质

与整数最小公倍数的联系：当两个分数的分母都为\(1\)时，分数的最小公倍数就等同于整数的最小公倍数。

例如，对于\(\frac{a}{1}\)和\(\frac{b}{1}\)，其最小公倍数就是\(\text{lcm}(a,b)\)。

通分性质：两个分数的最小公倍数可用于对这两个分数进行通分操作，使得它们分母相同。

例如，对于\(\frac{2}{3}\)和\(\frac{1}{4}\)，它们的最小公倍数是\(\frac{\text{lcm}(2,1)}{\gcd(3,4)}=\frac{2}{1}=2\)，将\(\frac{2}{3}\)和\(\frac{1}{4}\)分别化为以\(2\)为分母（实际操作中是化为以最小公倍数为分母）的分数，\(\frac{2}{3}=\frac{4}{6}\)，\(\frac{1}{4}=\frac{2}{8}\)，通过最小公倍数实现了通分，便于后续分数的运算等操作。

与最大公因数的关系：对于两个分数\(\frac{a}{b}\)和\(\frac{c}{d}\)，它们的乘积等于它们最大公因数与最小公倍数的乘积，即\(\frac{a}{b} \times \frac{c}{d}=\frac{\gcd(a,c)}{\text{lcm}(b,d)} \times \frac{\text{lcm}(a,c)}{\gcd(b,d)}\)，这和整数中最大公因数与最小公倍数的关系类似。