読者です 読者をやめる 読者になる 読者になる

ニ☆ウ☆ト☆ラ☆ボ

タイトルテスト中

不定方程式の整数解と最大公約数と: ユークリッドの互除法

簡単であるが, 因数分解することなく最大公約数が求まってしまうこの方法は, やはり面白い.

\( a > b > 0 \) を整数とし, \( a \) を \( b \) で割る: \[ a = q \, b + r, \quad 0 \le r < b. \] このとき, \[ \gcd(a, b) = \gcd(b, r). \]

証明はすこぶる簡単:

  1. \( d > 0 \) が \( a \) と \( b \) の公約数ならば, \( d \) は \( b \) と \( r \) の公約数.
  2. \( d > 0 \) が \( b \) と \( r \) の公約数ならば, \( d \) は \( a \) と \( b \) の公約数.
  3. したがって, \( a \) と \( b \) の公約数の集合と \( b \) と \( r \) の公約数の集合は一致.
  4. その中の最大のものも一致. 証明終.

こうして, 次のような計算が可能となる: 343 と 231 の最大公約数は, \begin{align} (343, 231) = (231, 112) = (112, 7) = (7, 0) = 7. \end{align} (煩わしいので, gcd は付けなかった.)

広告を非表示にする