Euclidの拡張互除法

質問

Euclidの拡張互除法

互いに素な自然数A,Bがあるとき、Ax+By=1を満たす整数(x,y)が存在しますね。
また、この式からAB-BA=0をn倍して辺々引くと A(x-nB)+B(y+nA)=1 が成り立つので
(x-nB,y+nA)も、Ax+By=1の整数解であると言えます。
これ以外に、Ax+By=1を満たす整数解は存在することはありますか?

それと、Euclidの拡張互除法で
Ax+By=1を満たす整数(x,y)を求めることができますが
無限に存在する(x,y)の組のうち、求まるのは
最も簡単なもののような気がしますが、それは正しいですか?

「最も簡単」というのは適当な表現が見つからないのですが
絶対値が一番小さい数の組み合わせといいますか
既約分数のようなイメージです。

回答No.1

mister_moonlight · ベストアンサー

＞これ以外に、Ax+By=1を満たす整数解は存在することはありますか?

質問の意図がわかりにくいが、一般解を求めておく。それで解決なんじゃないの？

xとyの特別解の一つを(α、β)とする。
ax＋by＝1　‥‥(1)　aα＋bβ＝1　‥‥(2)　であるから　(1)-(2)を作ると、a*(x-α)＝b*(β-y)となる。
aとbは互いに素から、mを整数として　x-α＝bm、β-y＝am 。
よって、(x、y)＝(bm＋α、β-am)。

お礼

補足の補足です
「aとbは互いに素」以降が自分はわかっていないようです。
互いに素だと、何故そのように書けるのでしょうか？

補足

回答ありがとうございます。
解いていただいた一般解以外にも解があるかどうかなんですが
この回答からでは、他に解が無いことがよくわかりません。

回答No.5

alice_44

＞ 必要条件だけを辿っていることを
＞ 回答者様の方で説明いただければ結構です。

普通のユークリッド互除法で
ベズーの等式の係数が求まることは、
A No.2 で説明しましたが。

補足

特殊解を求める手順についてはわかるのですが
一般解を求める手順が必要条件だけを辿っていることは
No.2の回答のどの辺りで説明していただいているのかわからないです。

回答No.4

alice_44

"拡張 互除法" でネット検索してみましたが、
出てくるのはプログラム関連のページばかりで、
数字のサイトを見かけません。
内容的にも、普通のユークリッド互除法について
書いてあるようです。
どこが「拡張」なのか、結局解りませんでした。
代数的な説明が必要であれば、
"べズー 互除法" で検索
してみることを勧めます。

補足

回答ありがとうございます。

サイトは結構ですので
必要条件だけを辿っていることを
回答者様の方で説明いただければ結構です。

＞どこが「拡張」なのか、結局解りませんでした。
単に最大公約数を求めるのが互除法
そこから、Ax+By=1の形にするのが拡張互除法
ではないのでしょうか?

回答No.3

noname#149523

>Euclidの拡張互除法
についてだけ。「拡張ユークリッドの互除法」or「拡張ユークリッド互除法」で検索したほうがたくさんヒットします。
www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html

「拡張～」のプログラムは謎の方法で書かれていることがあるので、自分で書く場合は手計算でのやり方をそのままプログラムにするというもの一つの手です。

補足

回答ありがとうございます。
自分の目的を達するためのプログラムは一応できているのですが(もちろんエラーチェック等色々な点でお粗末だとは思います)
今はむしろプログラムより数学的な意味の理解や応用面を知りたいと思っています。
検索するとプログラムが出てくることが多く、また拡張互除法以外の解を知りたいので、なかなか目的のサイトが見つかりません。

回答No.2

alice_44

No.1 は、文字の使い方が質問文と違うだけで、
同じ方程式の一般解を求め、それが
質問者の解で全てであることを示していますよ。
必要条件をたどって変形したのだから、
他には解はありません。
質問文の x, y, n が、
No.1 では α, β, -m と
書かれています。

「拡張互除法」って、何でしょう？
普通に互除法で A,B の最大公約数を求める際、
A を B で割った余りが C[1]、
B を C[1] で割った余りが C[2]、
C[1] を C[2] で割った余りが C[3]
…と続けていくと、出てくる C[ ] は、
どれも A と B の整数倍の和です。
そして、A と B が互いに素であれば、
どこかで余りが 1 になって終わります。
そこまでの C[ ] を、順次 jA+kB の形に
メモしながら計算を進めれば、
余りが 1 になった時点で、1 = xA+yB が得られます。

補足

回答ありがとうございます。
必要条件をたどっているのかどうかがわからないのです。
例えば私が質問文に書いた方法のうち「n倍して」が抜けていたら、もちろん他に解が存在することになります。
そのような“抜け”が本当に無いのかがよくわからないのです。

回答後半についてですが、手順だけは理解できていると思います。
質問文の後半は考えた末やっと「0<|y|<A,0<|x|<Bを満たすx,yの組が必ず1組だけ存在し、拡張互除法ではそれを求めている」という言葉になりました。