初等數論--整除--歐幾里得算法/輾轉相除法/更相減損術

• 歐幾里得算法/輾轉相除法/更相減損術

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

歐幾里得算法/輾轉相除法/更相減損術

$$\begin{gathered} 設a_0,a_1\in Z,a_1=0,按照以下步驟，反復作帶余除法： \\ {a}_0=a_{1}q+a_2,a_2<a_1 \\ {a}_1=a_{2}q+a_3,a_3<a_2 \\ {a}_2=a_{3}q+a_4,a_4<a_3 \\ \dots \dots \\ {a}_{n?2}=a_{n?1}q+a_n,a_n<a_{n?1} \\ {a}_{n?1}=a_{n}q+a_{n+1},a_{n+1}=0 \\ 我們需要證明，以上必為有限步，且(a_0,a_1)=a_n \end{gathered}$$

• $$\begin{gathered} 以上必為有限步： \\ 因為0<a_n<a_{n?1}<\dots <a_2<a_1<a_0, \\ 且a_0為整數，它的正整數是有限的, \\ 所以n是有限的 \end{gathered}$$
• $$\begin{gathered} (a_0,a_1)=a_n： \\ 我們已知(a,b)=(a,b+ax), \\ 則(a_0,a_1)=(a_0?a_{1}q,a_1)=(a_2,a_1)=(a_1,a_2), \\ 同理，(a_1,a_2)=(a_2,a_3),(a_2,a_3)=(a_3,a_4)\dots \dots \\ 最終我們得到(a_0,a_1)=(a_{n?1},a_n)=a_n \end{gathered}$$

總結

以上是生活随笔為你收集整理的初等数论--整除--欧几里得算法/辗转相除法/更相减损术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。