ユークリッドの互除法

定義 3.1（「整除と素因数分解」§3）

正の整数 $a>b$ に対し、 $r_{-1}=a$ , $r_0=b$ とおき、 $r_i>0$ である限り、除法の原理で

r_{i-1}=q_i\,r_i+r_{i+1},\qquad 0\le r_{i+1}<r_i\qquad(i=0,1,2,\ldots)

と商 $q_i$ と余り $r_{i+1}$ を定める。余りが初めて $0$ になる、すなわち $r_{n+1}=0$ となる $n$ を段数といい（余りが $0$ になる最後の割り算を含めて、割り算は $n+1$ 回行われる）、この手順をユークリッドの互除法という。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

証明で明示的に参照している定理は、まだありません。