ある整数xとyの最小公倍数を出す計算をして結果を眺めていたら、ある法則がある事がわかった。 xとyをそれぞれ素因数分解して、xの素因数リストとyの素因数リストを出し、 xの素因数リストとyの素因数リストの重複部分を打ち消し、 残ったxの素因数リストを…

前回のエントリで最小公倍数を出す法則を見つけたが、その過程で最大公約数を出している事が分かった。xとyの素因数リストの中にある重複部分を掛けた結果が最大公約数。 重複した部分が無い場合は1が最大公約数。 xとyをそれぞれ素因数分解して、xの素因数…

2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余…