ここから本文です

ユークリッドの互除法を用いて不定方程式を解く方法をわかりやすく教えて下さい。

sip********さん

2012/3/514:07:27

ユークリッドの互除法を用いて不定方程式を解く方法をわかりやすく教えて下さい。

閲覧数:
842
回答数:
1
お礼:
25枚

違反報告

ベストアンサーに選ばれた回答

ebt********さん

2012/3/517:33:41

a, b を0でない整数とし、g = ged(a, b) (最大公約数) とおきます。
さらに、a/g = A, b/g = B, とおきます。

次の不定方程式を考えます。
ax + by = mg(mは整数)

この方程式を満たす解は無数にありますが、ひとつは探します。
x = x[1], y = y[1] が解であるとしましょう。
解が一つわかると、この不定方程式のすべての解が求められます。
それは、整数kを x = x[1] + kA, y = y[1] + bk に代入することで得られます。


具体例を見てみましょう。
a = 123456789, b = 987654321とします。
g = ged(123456789, 987654321) = 9 で、
A = 123456789/9 = 13717421
B = 987654321/9 = 109739369
m = 123456789 として、不定方程式
123456789x + 987654321y = 1111111101をかんがえると、
一つの解は、x = 9, y = 0 です。
解が一つわかると、この不定方程式のすべての解が求められます。
それは、整数kを 、
x = 9 + 123456789k, y = 987654321k に代入することで得られます。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる