求证：当gcd(k,b)=1时，gcd(ka,b)=gcd(a,b)的思路求助

嘿，我来帮你把这个证明的逻辑理清楚，其实你已经找对了核心工具（贝祖引理），咱们只需要把它用到两个方向的整除关系上就行：

第一步：证明 $\gcd(ka, b)$ 整除 $\gcd(a, b)$ #

设 $d = \gcd(ka, b)$，根据最大公约数的定义，$d$ 满足：

• $d \mid ka$（$d$ 整除 $ka$）
• $d \mid b$（$d$ 整除 $b$）

已知 $k$ 和 $b$ 互质，根据贝祖引理，存在整数 $x, y$ 使得：
$$xk + yb = 1$$

把这个等式两边同时乘以 $a$，得到：
$$xka + yba = a$$

现在看右边的 $a$：

• 因为 $d \mid ka$，所以 $d \mid xka$；
• 因为 $d \mid b$，所以 $d \mid yba$；

两个被 $d$ 整除的数相加，结果也能被 $d$ 整除，所以 $d \mid a$。

既然 $d$ 同时整除 $a$ 和 $b$，那 $d$ 肯定是 $a$ 和 $b$ 的公约数，自然就有 $d \mid \gcd(a, b)$。

第二步：证明 $\gcd(a, b)$ 整除 $\gcd(ka, b)$ #

设 $d' = \gcd(a, b)$，根据定义：

• $d' \mid a$，所以 $d' \mid ka$（因为 $a$ 是 $ka$ 的因数）；
• $d' \mid b$；

这说明 $d'$ 是 $ka$ 和 $b$ 的公约数，所以 $d' \mid \gcd(ka, b)$。

最后：得出结论 #

现在我们有：

• $\gcd(ka, b) \mid \gcd(a, b)$
• $\gcd(a, b) \mid \gcd(ka, b)$

两个正整数互相整除，那它们必然相等，所以：
$$\gcd(ka, b) = \gcd(a, b)$$

内容的提问来源于stack exchange，提问作者SS'