设 a 0 , a 1 ∈ 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 … … 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 设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=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
以 上 必 为 有 限 步 ： 因 为 0 < a n < a n − 1 < … < a 2 < a 1 < a 0 , 且 a 0 为 整 数 ， 它 的 正 整 数 是 有 限 的 , 所 以 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是有限的 ( a 0 , a 1 ) = a n ： 我 们 已 知 ( a , b ) = ( a , b + a x ) , 则 ( 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 (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−a1q,a1)=(a2,a1)=(a1,a2),同理，(a1,a2)=(a2,a3),(a2,a3)=(a3,a4)……最终我们得到(a0,a1)=(an−1,an)=an