最大公约数证明问询：求证d是a,b公因子当且仅当d∣g

我正在梳理这个数论问题的证明思路：

设$a,b \in \mathbb{Z}$且不全为0，$g = \gcd(a,b)$。证明$d$是$a$和$b$的公因子当且仅当$d \mid g$。

必要性方向（$\Longrightarrow$：公因子必整除最大公约数） #

已知$\gcd(a,b)=g$，根据最大公约数的定义，首先有$g \mid a$且$g \mid b$。再结合贝祖定理，我们知道存在整数$x,y \in \mathbb{Z}$，满足：
$$ax + by = g$$
现在假设$d$是$a$和$b$的公因子，也就是$d \mid a$且$d \mid b$。根据整除的性质，若一个数能整除两个整数，那么它也能整除这两个整数的任意线性组合。所以$d$必然能整除$ax + by$，也就是$d \mid g$，这就完成了必要性的证明。

充分性方向（$\Longleftarrow$：整除最大公约数的数必是公因子） #

接下来证明反向逻辑：如果$d \mid g$，那么$d$是$a$和$b$的公因子。
首先，$g$是$a$和$b$的最大公约数，根据定义，$g$本身就是$a$和$b$的公因子——也就是$g \mid a$且$g \mid b$。而整除具有传递性：

• 由$d \mid g$且$g \mid a$，可直接推出$d \mid a$；
• 同理，由$d \mid g$且$g \mid b$，可推出$d \mid b$。
  这就说明$d$同时整除$a$和$b$，也就是$d$是$a$和$b$的公因子，充分性得证。

至此，双向推导都完成，题目中的等价关系得证。

内容的提问来源于stack exchange，提问作者John W. Smith