数学 › 数論 › 整除と素因数分解

互除法の正しさと拡張

定理 3.2（「整除と素因数分解」§3） ・ ✓公理まで証明済み

互除法の最後の非零の余り rnr_n は gcd⁡(a,b)\gcd(a,b) に等しい。さらに、整数列 si,tis_i,t_i を

s−1=1, t−1=0,s0=0, t0=1,si+1=si−1−qisi,ti+1=ti−1−qitis_{-1}=1,\ t_{-1}=0,\quad s_0=0,\ t_0=1,\qquad s_{i+1}=s_{i-1}-q_i s_i,\quad t_{i+1}=t_{i-1}-q_i t_i

で定めると、すべての ii について ri=a si+b tir_i=a\,s_i+b\,t_i が成り立つ。特に gcd⁡(a,b)=a sn+b tn\gcd(a,b)=a\,s_n+b\,t_n である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

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

前提をたどる 証明が使う定理・定義

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

これを使っている定理 証明で参照している 2 件

関連するノック 5 問