关于整数线性组合与公约数整除性的证明问询

这是数论入门里的核心整除性质，咱们用最基础的定义一步步推导就能搞定：

第一步：明确公约数的定义 #

因为d是a和b的公约数，根据整数整除的定义，必然存在两个整数k₁和k₂，满足：

• a = d × k₁
• b = d × k₂

第二步：代入线性组合展开 #

把上面a和b的表达式代入任意线性组合ma + nb（其中m、n都是整数）：

ma + nb = m×(d×k₁) + n×(d×k₂)

第三步：提取公因子并验证整数性 #

我们可以把公因子d提取出来，得到：

ma + nb = d × (m×k₁ + n×k₂)

这里要注意：m、n、k₁、k₂都是整数，而整数的加法和乘法运算结果仍然是整数，所以m×k₁ + n×k₂肯定是某个整数，咱们把它记作k（即k = m×k₁ + n×k₂，且k ∈ ℤ）。

第四步：应用整除定义得出结论 #

现在我们得到了ma + nb = d × k，其中k是整数。根据整除的定义：如果存在整数k使得x = d×k，那么d整除x（记作d | x）。

所以直接就能得出结论：d | (ma + nb)。

补充一句：这个性质是欧几里得算法求最大公约数的核心依据之一，也是后续解决线性丢番图方程的基础，理解它能帮你打通很多数论入门的知识点~

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