2018-07-01から1日間の記事一覧
ユークリッドの互除法:a>bでaとbを正の整数とする。a mod b ≠ 0 ⇒ gcd(a,b) = gcd(b,a mod b) [証明]gcd(a,b) = gとおくと、互いに素なk,mを用いて、a = gk , b = gmと置ける。gkをgmで割った時の商をQ、余りをRとするとき、gk = Qgm + Rとおけるから、R = …
ユークリッドの互除法:a>bでaとbを正の整数とする。a mod b ≠ 0 ⇒ gcd(a,b) = gcd(b,a mod b) [証明]gcd(a,b) = gとおくと、互いに素なk,mを用いて、a = gk , b = gmと置ける。gkをgmで割った時の商をQ、余りをRとするとき、gk = Qgm + Rとおけるから、R = …