[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→
不定方程式ax+by=dの特殊解の求め方(互除法による)
Copyright (C) virtual_high_school, 2017
【音声入り動画による説明】
【パラパラ・マンガによる説明】
←
パラパラまんが
自然数a と b に対し、その最大公約数を d とするとき
$ ax+by=d $
の特殊解$x,y $の求め方。
【アルゴリズム】
まず、ユークリッドの互除法で2数の最大公約数(dになるわけだが)を求める。
その求め方は、別のページ 「最大公約数の求め方(互除法による)」に書いた。
そうすると、割り算の上辺に商の列(左から) $ q_{1}, q_{2}, q_{3},\cdots, q_{n}$ が並ぶ。
この商に列に対して、以下のアルゴリズムを実行する。
商の列の、最後と最後から2番目の数$ q_{n-1}, q_{n}$ が特殊解から符号を除いたものである。
a,b とたすき掛けを行うと、
$ a \times q_{n-1} - b \times q_{n} = \pm 1$
になるので、
(ア) $1$ ならば $x=q_{n-1},y=-q_{n}$
(イ) $-1$ ならば $x=-q_{n-1},y=q_{n}$
が特殊解になる。
[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→