模算术整除性证明：已知as≡b mod n，求证gcd(a,n)整除b

你的初始推导方向是完全正确的，只是在后续步骤中没必要引入额外的整数变量（$k_2$、$k_3$），反而把问题绕复杂了。咱们把推导拉回核心逻辑，几步就能完成证明：

步骤1：从同余式转化为等式 #

已知整数$a,b,n,s$满足 $as \equiv b \mod n$，根据同余的定义，必然存在整数$k_1$，使得：
$$as = k_1 n + b$$

步骤2：提取最大公约数并分析整除性 #

设$d = \gcd(a,n)$，根据最大公约数的定义：

• $d \mid a$（$d$整除$a$），因此$d \mid as$（$d$整除$a$的任意整数倍）
• $d \mid n$（$d$整除$n$），因此$d \mid k_1 n$（$d$整除$n$的任意整数倍）

步骤3：通过线性组合完成证明 #

把步骤1的等式变形，将$b$单独放在一侧：
$$b = as - k_1 n$$
根据整除的性质：如果一个数能整除两个整数，那么它也能整除这两个整数的任意线性组合（和或差）。
这里$d$既整除$as$，又整除$k_1 n$，所以$d$必然整除它们的差$as - k_1 n$，也就是：
$$d \mid b$$
而$d = \gcd(a,n)$，因此$\gcd(a,n)$整除$b$，证明完成。

补充说明你之前的小弯路 #

你之前引入$as = k_2 d$和$k_1 n = k_3 d$代入后得到$as = k_3 d + b$，其实只要把这个等式再变形为$b = as - k_3 d$，结合$k_3 d = k_1 n$，就回到了上面的核心式子$b = as - k_1 n$——本质是一样的，只是多绕了一层变量，反而不如直接移项来得直观。

内容的提问来源于stack exchange，提问作者Matt Robbins