初等數(shù)論--整除--公因數(shù)一定是最大公因數(shù)的因數(shù)

• 最大公因數(shù)
• 互素
• 公因數(shù)一定是最大公因數(shù)的因數(shù):$d|a且d|b?d|(a,b)$

博主本人是初學(xué)初等數(shù)論（整除+同余+原根），本意是想整理一些較難理解的定理、算法，加深記憶也方便日后查找；如果有錯(cuò)，歡迎指正。
我整理成一個(gè)系列： 初等數(shù)論，方便檢索。

最大公因數(shù)

$d=(a,b)$
$$滿足兩個(gè)條件：\{\begin{array}{r}d|a且d|b\\ 對(duì)整數(shù)c,如果c|a且c|b，有c\le d\end{array}$$

互素

$(a,b)=1$

公因數(shù)一定是最大公因數(shù)的因數(shù):$d|a且d|b?d|(a,b)$

$證明：$
$通過(guò)輾轉(zhuǎn)相除法，我們知道(a,b)=at+bs,?t,s\in Z,即a,b的最大公因數(shù)可以寫(xiě)成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$

總結(jié)

以上是生活随笔為你收集整理的初等数论--整除--公因数一定是最大公因数的因数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。