信息安全数学基础--整除--欧几里得算法/辗转相除法/更相减损术
- 欧几里得算法/辗转相除法/更相减损术
欧几里得算法/辗转相除法/更相减损术
设a0,a1∈Z,a1≠0,按照以下步骤，反复作带余除法：a0=a1q+a2,a2<a1a1=a2q+a3,a3<a2a2=a3q+a4,a4<a3……an?2=an?1q+an,an<an?1an?1=anq+an+1,an+1=0我们需要证明，以上必为有限步，且(a0,a1)=an设a_{0},a_{1}\in Z,a_{1}\neq 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}\\ ……\\ 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}设a0?,a1?∈Z,a1???=0,按照以下步骤，反复作带余除法：a0?=a1?q+a2?,a2?<a1?a1?=a2?q+a3?,a3?<a2?a2?=a3?q+a4?,a4?<a3?……an?2?=an?1?q+an?,an?<an?1?an?1?=an?q+an+1?,an+1?=0我们需要证明，以上必为有限步，且(a0?,a1?)=an?
- 以上必为有限步：因为0<an<an?1<…<a2<a1<a0,且a0为整数，它的正整数是有限的,所以n是有限的以上必为有限步：\\因为0<a_{n}<a_{n-1}<…<a_{2}<a_{1}<a_{0},\\且a_{0}为整数，它的正整数是有限的,\\ 所以n是有限的以上必为有限步：因为0<an?<an?1?<…<a2?<a1?<a0?,且a0?为整数，它的正整数是有限的,所以n是有限的
- (a0,a1)=an：我们已知(a,b)=(a,b+ax),则(a0,a1)=(a0?a1q,a1)=(a2,a1)=(a1,a2),同理，(a1,a2)=(a2,a3),(a2,a3)=(a3,a4)……最终我们得到(a0,a1)=(an?1,an)=an(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})……\\ 最终我们得到(a_{0},a_{1})=(a_{n-1},a_{n})=a_{n}(a0?,a1?)=an?：我们已知(a,b)=(a,b+ax),则(a0?,a1?)=(a0??a1?q,a1?)=(a2?,a1?)=(a1?,a2?),同理，(a1?,a2?)=(a2?,a3?),(a2?,a3?)=(a3?,a4?)……最终我们得到(a0?,a1?)=(an?1?,an?)=an?