数论2：最大公因子及其性质

数论2：最大公因子及其性质"/>

数论2：最大公因子及其性质

最大公因子及其性质

如果 A A A 和 B B B 为不全为 0 0 0，则它们的公因子的集合是一个有限的整数集，通常包括 + 1 +1 +1 和 − 1 -1 −1，我们对其中最大的那个公因子感兴趣。

定义2

不全为 0 0 0 的整数 A A A 和 B B B 的最大公因子是指能够同时整除 A A A 和 B B B 的最大整数。
A A A 和 B B B 的最大公因子记作 g c d ( A , B ) gcd(A, B) gcd(A,B)。
g c d ( 0 , N ) = N gcd(0, N) = N gcd(0,N)=N，虽然所有的正整数都能整除 0 0 0，我们还是定义 g c d ( 0 , 0 ) = 0 gcd(0, 0) = 0 gcd(0,0)=0。（这样可以确保关于最大公因子的相关结论在所有情况下均成立。）
例如： 24 24 24 和 84 84 84 的公因子有 ± 1 \pm 1 ±1、 ± 2 \pm2 ±2、 ± 3 \pm3 ±3、 ± 4 \pm4 ±4、 ± 6 \pm6 ±6、 ± 12 \pm12 ±12，因此 g c d ( 24 , 84 ) = 12 gcd(24, 84) = 12 gcd(24,84)=12。类似的，通过查看公因子集合，我们有 g c d ( 0 , 44 ) = 44 gcd(0, 44)=44 gcd(0,44)=44， g c d ( − 6 , − 15 ) = 3 gcd(-6, -15) = 3 gcd(−6,−15)=3， g c d ( − 17 , 289 ) = 17 gcd(-17, 289) = 17 gcd(−17,289)=17

定义3

设 A A A、 B B B 均为非 0 0 0 整数，如果 A A A 和 B B B 的最大公因子 g c d ( A , B ) = 1 gcd(A, B)=1 gcd(A,B)=1，则称 A A A 与 B B B 互质。
注意由于 − A -A −A 的因子与 A A A 的因子相同，故有 g c d ( A , B ) = g c d ( ∣ A ∣ , ∣ B ∣ ) gcd(A, B) = gcd(\vert A\vert, \vert B\vert) gcd(A,B)=gcd(∣A∣,∣B∣)，其中 $ \vert A \vert$ 表示 A A A 的绝对值，因此，我们只关注正整数对的最大公因子。

定理4

A A A、 B B B 是整数，且 g c d ( A , B ) = D gcd(A, B) = D gcd(A,B)=D，那么 g c d ( A ÷ D , B ÷ D ) = 1 gcd(A\div D, B\div D) = 1 gcd(A÷D,B÷D)=1。

证明

已知 A A A、 B B B 是整数，且 g c d ( A , B ) = D gcd(A, B) = D gcd(A,B)=D。我们将证明 A ÷ D A\div D A÷D、 B ÷ D B\div D B÷D 除了 1 1 1 之外没有其他的公因子。假设还有正整数 E E E 使得 E ∣ ( A / D ) E \mid (A / D) E∣(A/D) 且 E ∣ ( B / D ) E \mid (B / D) E∣(B/D)。
那么存在整数 K K K 和 L L L 使得 A ÷ D = K E A \div D = KE A÷D=KE， B ÷ D = L E B \div D = LE B÷D=LE，于是 A = D E K A = DEK A=DEK， B = D E L B = DEL B=DEL。因此 D E DE DE 是 A A A、 B B B 的公因子，因为 D D D 是 A A A、 B B B 的最大公因子，故 D E ⩽ D DE \leqslant D DE⩽D，于是 E = 1 E = 1 E=1。
因此 g c d ( A ÷ D , B ÷ D ) = 1 gcd(A \div D, B \div D) = 1 gcd(A÷D,B÷D)=1。

推论 1

如果 A A A、 B B B 为整数，且 B ≠ 0 B \neq 0 B=0，则 A ÷ B = P ÷ Q A \div B = P \div Q A÷B=P÷Q，其中 P P P、 Q Q Q 为整数，且 g c d ( P , Q ) = 1 gcd(P, Q) = 1 gcd(P,Q)=1， Q ≠ 0 Q \neq 0 Q=0。

证明

假设 A A A、 B B B 为整数且 B ≠ 0 B \neq 0 B=0，令 P = A ÷ D P = A \div D P=A÷D， Q = B ÷ D Q = B \div D Q=B÷D，其中 D = g c d ( A , B ) D = gcd(A, B) D=gcd(A,B)，则 P ÷ Q = ( A ÷ D ) ÷ ( B ÷ D ) P \div Q = (A \div D) \div (B \div D) P÷Q=(A÷D)÷(B÷D)，由定理4可知 g c d ( P , Q ) = 1 gcd(P, Q) = 1 gcd(P,Q)=1，命题得证。

定理5

令 A A A、 B B B、 C C C 是整数，那么 g c d ( A + C B , B ) = g c d ( A , B ) gcd(A+CB, B) = gcd(A, B) gcd(A+CB,B)=gcd(A,B)。

证明

令 E E E 是 A A A、 B B B的公因子，由定理2可知 E ∣ ( A + C B ) E \mid (A + CB) E∣(A+CB)，所以 E E E 是 A + C B A + CB A+CB 和 B B B 的公因子。
如果 F F F 是 A + C B A + CB A+CB 和 B B B 的公因子，由定理2可知 F F F 整除 ( A + C B ) − C B = A (A + CB) - CB = A (A+CB)−CB=A，所以 F F F 是 A A A、 B B B 的公因子，因此 g c d ( A + C B , B ) = g c d ( A , B ) gcd(A + CB, B) = gcd(A, B) gcd(A+CB,B)=gcd(A,B)。

定义4

如果 A A A、 B B B 是整数，那么它们的线性组合具有形式 M A + N B MA + NB MA+NB，其中 M M M、 N N N 都是整数。

定理6

两个不全为 0 0 0 的整数 A A A、 B B B 的最大公因子是 A A A、 B B B 的线性组合中最小的正整数。

证明

令 D D D 是 A A A、 B B B 的线性组合中最小的正整数， D = M A + N B D = MA + NB D=MA+NB，其中 M M M、 N N N 是整数，我们将证明 D ∣ A D \mid A D∣A、 D ∣ B D \mid B D∣B。
由带余除法，得到 A = D Q + R A = DQ + R A=DQ+R， 0 ⩽ R < D 0\leqslant R < D 0⩽R<D。
由 A = D Q + R A = DQ + R A=DQ+R 和 D = M A + N B D = MA + NB D=MA+NB，得到 R = A − D Q = A − Q ( M A + N B ) = ( 1 − Q M ) A − Q N B R = A - DQ = A - Q(MA + NB) = (1 - QM)A-QNB R=A−DQ=A−Q(MA+NB)=(1−QM)A−QNB。
这就证明了整数 R R R 是 A A A、 B B B 的线性组合。因为 0 ⩽ R < D 0 \leqslant R < D 0⩽R<D，而 D D D 是 A A A、 B B B 的线性组合中最小的正整数，于是我们得到 R = 0 R = 0 R=0 （如果 R ≠ 0 R \neq 0 R=0，那意味着 R R R 才是所有线性组合中最小的正整数，这与 D D D 是所有线性组合中最小的正整数矛盾），因此 D ∣ A D \mid A D∣A，同理可得， D ∣ B D \mid B D∣B。
我们证明了 A A A、 B B B 的线性组合中最小的正整数 D D D 是 A A A、 B B B 的公因子，剩下要证的事它是 A A A、 B B B 的最大公因子，为此只需证明 A A A、 B B B 所有的公因子都能整除 D D D。
由于 D = M A + N B D = MA + NB D=MA+NB，因此如果 C ∣ A C \mid A C∣A 且 C ∣ B C \mid B C∣B，那么由定理2有 C ∣ D C \mid D C∣D，因此 D > C D >C D>C，这就完成了证明。

定义5

令 A 1 A_1 A1​,、 A 2 A_2 A2​、 … \dots …、 A N A_N AN​ 是不全为 0 0 0 的整数，这些整数的公因子中最大的整数就是最大公因子。
A 1 A_1 A1​,、 A 2 A_2 A2​、 … \dots …、 A N A_N AN​ 的最大公因子记为 g c d ( A 1 , A 2 , … , A N ) gcd(A_1,A_2,\dots,A_N) gcd(A1​,A2​,…,AN​)。（注意 A i A_i Ai​ 在这里面出现的顺序并不影响结果。)

引理1

如果 A 1 A_1 A1​、 A 2 A_2 A2​、 … \dots …、 A N A_N AN​，是不全为 0 0 0 的整数，那么 g c d ( A 1 , A 2 , … , A N − 1 , A N ) = g c d ( A 1 , A 2 , … , g c d ( A N − 1 , A N ) ) gcd(A_1, A_2, \dots, A_{N-1}, A_N) = gcd(A_1, A_2, \dots, gcd(A_{N-1}, A_N)) gcd(A1​,A2​,…,AN−1​,AN​)=gcd(A1​,A2​,…,gcd(AN−1​,AN​))。

证明

N N N 个整数 A 1 A_1 A1​、 A 2 A_2 A2​、 … \dots …、 A N A_N AN​ 的任意公因子也是 A N − 1 A_{N-1} AN−1​ 和 A N A_N AN​ 的公因子，因此也是 g c d ( A N − 1 , A N ) gcd(A_{N-1}, A_N) gcd(AN−1​,AN​) 的因子。
同样 N − 2 N-2 N−2 个整数 A 1 A_1 A1​、 A 2 A_2 A2​、 … \dots …、 A N − 2 A_{N-2} AN−2​ 和 g c d ( A N − 1 , A N ) gcd(A_{N-1}, A_N) gcd(AN−1​,AN​) 的公因子也是 N N N 个整数 A 1 A_1 A1​、 A 2 A_2 A2​、 … \dots …、 A N A_N AN​ 的公因子，因为如果某整数整除 g c d ( A N − 1 , A N ) gcd(A_{N-1}, A_N) gcd(AN−1​,AN​)，那么它一定同时整除 A N − 1 A_{N-1} AN−1​ 和 A N A_N AN​。
因此，这 N N N 个整数的公因子由前 N − 2 N-2 N−2 个整数与后两个整数组成的集合的公因子完全相同，它们的最大公因子也一定相同。