ユークリッドの互除法を用いて解く問題がわかりません

質問

２題あるのですが
（１）299x＋323y＝1を満たす整数x、yの組を一組求める
（２）（d・e）-1がaで割り切れるようなeを求める
という問題です。
考えたのですが、答えを導出できませんでした。
導出過程と答えを教えてください。よろしくお願いします

回答No.7

noname#101087

一般解担当？の #2 です。

17*e - 2132*f = 1　の一つの解が {eo, fo} = {-627, -5} なのですね。

一般解は、
　e = eo + 2132*k
　f = fo + 17*k

　k=1 : e = 1505, f = 12
　k=2 : e = 3637, f = 29
　k=3 : e = 5769, f = 46
　k=4 : e = 7901, f = 63
…あともぞろぞろ、みたいです。

回答No.6

sinisorsa

>でも、これでは(17・（－627）)－１が２１３２で割り切れないのですが・・・
>もしeに627を用いる場合は(17・(-627))+1が2132で割り切れそうです
>やはり６２７ではないのでしょうか？

17・(-627)-1=-10659-1=-10660=-5*2132

ですから、2132で割り切れていますよ。
やはり、ｅ＝－６２７ですよ。もう一度計算してみてください。

回答No.5

sinisorsa

＃４の続きです。
（２）の方も導出してみましょう。
ユークリッドの互除法を実行します。
［１］２１３２＝１２５×１７＋７
［２］　　１７＝　　２×７＋３
［３］　　　７＝　　２×３＋１
これで、最大公約数は１となることが分かります。
［３］より　１＝７－２×３
　最後の３に［２］から１７－２×７を代入します。
すると、　１＝７－２×（１７－２×７）
　　　　　　＝－２×１７＋５×７
　最後の７に［１］から２１３２－１２５×１７を代入します。
すると、
　１＝－２×１７＋５×（２１３２－１２５×１７）
　　＝５×２１３２－（２＋５×１２５）×１７
　　＝５×２１３２－６２７×１７
従って　ｅ＝－６２７
こんな風にするとよいと思います。

お礼

ありがとうございます

でも、これでは(17・（－627）)－１が２１３２で割り切れないのですが・・・
もしeに627を用いる場合は(17・(-627))+1が2132で割り切れそうです
やはり６２７ではないのでしょうか？

回答No.4

sinisorsa

d=17, a=2132とすると、dとaの最大公約数は１になります。
17e-1が2132で割り切れるということは、商をqとして、17e-1=2132q
となることです。（余りが０といことです。）
この式を変形すると、17e-2132q=1
17x+2132y=1と同じ形ですから、これを満たす、xとyを求めればよいわけです。
xがeになります。

やり方は、（１）の私の解法と同じですので、ご自分でやってみましょう。
問題（１）も（２）は、質問のタイトルにあるようにユークリッドの
互除法を用いて解くことが前提になっていると思います。（出題者の意図）
従って、他の方法で答えを発見してもだめだと思います。
私が出題者なら、問題をしっかり読みなさいと赤字で書き込みますね。

回答No.3

mister_moonlight

＞（１）299x＋323y＝1を満たす整数x、yの組を一組求める

ユークリッドを持ち出す必要もない。

299x＋323y＝299（x＋y）＋24y＝1　より、x＋y＝aとすると、299a＋24y＝24（y＋12a）＋11a＝1.
y＋12a＝bとすると、24b＋11a＝11（a＋2b）＋2b＝1。
a＋2b＝cとすると、11c＋2b＝1　→　（b、c）＝（6、-1）。
よって、a＝c-2b＝-13。y＝b-12a＝162。x＝a-y＝-175.

（x、y）＝（-175、162）は確かに、299x＋323y＝1を満たす。

お礼

回答ありがとうございます
確かに条件通りの値を得られていますね！

回答No.2

noname#101087

>（１）299x＋323y＝1を満たす整数x、yの組を一組求める
#1 さんの結果
　　↓
　xo = 148, yo = -137
念のため、非負解(x,y ともに)の有無を調べてみると「無し」でした。

一般解は、
　xk = xo - 323*k, yk = yo + 299*k
ですが、
　x1 = -175, y1 = 162
非負解があるとすれば、xo, x1 の間。
つまり「無し」。

>（２）（d・e）-1 がaで割り切れるようなeを求める
a, d が所与(整数)として不定方程式
　d*x + a*y = 1
を考えれば、解 x が e を与える、ということかな。

お礼

回答ありがとうございます。
自然数だけの解があるかどうかを確認してくださったわけですね

（２）についてなんですが、完全にdとaを定義し忘れていました。
設問ではｄは17、aは2132となっていました

回答No.1

sinisorsa

（２）は問題の意味不明。a,d,eが未定義です。
（１）だけ、導出しましょう。

まず、　３２３と２９９に対して、互除法を適用します。
[1]３２３＝１×２９９＋２４
[2]２９９＝１２×２４＋１１
[3]　２４＝　２×１１＋　２
[4]　１１＝　５×２　＋１
従って、最大公約数は１である。すなわち互いに素である。
次にこの過程を逆に使います。
[4]から　１＝１１－５×２
[3]から　２＝２４－２×１１　これを上に代入すると
　　　　１＝１１－５×（２４－２×１１）
　　　　　＝－５×２４＋１１×１１
[2]から　１１＝２９９－１２×２４　これを上に代入する
　　　　１＝－５×２４＋１１×（２９９－１２×２４）
　　　　　＝１１×２９９－（－５－１１×２４）
　　　　　＝１１×２９９－１３７×２４
[1]から　２４＝３２３－１×２９９　これを上に代入して、
　　　　１＝１１×２９９－１３７×（３２３－１×２９９）
　　　　　＝－１３７×３２３＋１４８×２９９
すなわち、ｘ＝１４８、ｙ＝－１３７
となります。
検算すれば、合っていることが分かります。

お礼

（１）についてありがとうございます。
確かに（２）のa,dが未定義でした。すみません
例えばdを17、aを2132とした場合はどうなるでしょうか？