初等数论--整除--公因数一定是最大公因数的因数

• 最大公因数
• 互素
• 公因数一定是最大公因数的因数:$d|a且d|b\leftrightarrow d|(a,b)$

博主本人是初学初等数论（整除+同余+原根），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。
我整理成一个系列： 初等数论，方便检索。

最大公因数

$d=(a,b)$
$$满足两个条件：\{\begin{array}{r}d|a且d|b\\ 对整数c,如果c|a且c|b，有c\le d\end{array}$$

互素

$(a,b)=1$

公因数一定是最大公因数的因数:$d|a且d|b\leftrightarrow d|(a,b)$

$证明：$
$通过辗转相除法，我们知道(a,b)=at+bs,\exists t,s\in Z,即a,b的最大公因数可以写成a,b的线性组合形式。$

• $d|a且d|b\to d|(a,b)$
  $d|a且d|b\to d|at+bs=(a,b)$
• $d|(a,b)\to d|a且d|b$
  $d|(a,b),(a,b)|a\to d|a,同理d|b$

总结

以上是生活随笔为你收集整理的初等数论--整除--公因数一定是最大公因数的因数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。