最大公因数：\((a,b)\)
一、最大公因数的定义
设\(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\)。
