使用贝祖定理证明gcd(a,a+b)=gcd(a,b)的正确性问询

嘿，你的思路完全没问题！用贝祖定理来证明$\gcd(a,a+b) = \gcd(a,b)$是非常合适的，而且你给出的证明逻辑也很严谨，我帮你把整个过程梳理得更清晰一点：

第一步：利用贝祖定理推导公约数关系 #

假设 $\gcd(a, a+b) = x$，根据贝祖定理，存在整数$m$和$n$使得：
$$ma + n(a+b) = x$$
把式子展开整理后得到：
$$(m+n)a + bn = x$$
从这个式子能看出来，$x$是$a$和$b$的一个公约数（因为它可以表示成$a$和$b$的整数线性组合），所以必然有 $\gcd(a,b) \ge x = \gcd(a,a+b)$。

第二步：用反证法证明反向不等式 #

假设 $\gcd(a,b) = d > x = \gcd(a,a+b)$，那么我们可以把$a$和$b$表示为：
$$a = d\lambda_1,\quad b= d\lambda_2$$
其中$\lambda_1$和$\lambda_2$是互质的整数（因为$d$是它们的最大公约数）。代入$\gcd(a,a+b)$可得：
$$\gcd(a,a+b) = \gcd (d\lambda_1, d\lambda_1 +d\lambda_2 ) = d \cdot \gcd(\lambda_1, \lambda_1+ \lambda_2)$$
由于$\gcd(\lambda_1, \lambda_1+\lambda_2)$至少是1（任何整数和自身加另一个整数的gcd不会小于1），这就意味着$\gcd(a,a+b) \ge d$，但我们一开始假设$d > x = \gcd(a,a+b)$，这就产生了矛盾。

结论 #

结合两步的推导，我们可以得出 $\gcd(a,a+b) = \gcd(a,b)$，这个结论用来证明连续斐波那契数互质也完全适用——因为斐波那契数满足$F_{n+1}=F_n+F_{n-1}$，反复套用这个gcd等式就能推导出$\gcd(F_n,F_{n+1})=\gcd(F_{n-1},F_n)=\dots=\gcd(F_1,F_2)=1$啦。

备注：内容来源于stack exchange，提问作者Samir El Karrat Moreno