109x-29y=1 の整数解の見つけ方（互除法を使わず）

Question

109x-29y=1 の整数解の１つを求めたいのですが、何か賢い方法はあるでしょうか。

ユークリッドの互除法を利用すれば (x,y)=(4,15) が１つの整数解になることがわかりますが、
互除法を使わずに解に迫る方法はありますか？

109の倍数：109 218 327 436 545 654 763 872 981 1090 …
29の倍数：29 58 87 116 145 174 203 232 261 290 …

kairou · Accepted Answer

NO7 に対する 補足文に対して。

9x1=9, 9x2=18, 9x3=27, 9x4=36,・・・ ですから、
1桁目だけを考えると x の１桁目に +1 をすると y の １桁目になる筈です。

又 29x3<109<29x4 ですから、１桁目だけを考えれば、
3x<y<4x ; y=x+1 を満たす 整数の筈です。
（ごめんなさい 102 は ミスタイプでした。）
x=1 の時は 3<y<4 で これを満たす 整数は ありません。
x=2 の時は 6<y<8 で 2+1≠7 で ダメです。
x=3 の時は 9<y12 で １桁目が 4 にはなりませんから ダメです。
x=4 の時は 12<y<16 で , y の候補は 15,25,35, ・・・になり、
y=15 が 題意を満足することが分かります。

「互除法を使わずに解に迫る方法」と言う事ですから、
無理やり考えた結果です。
この問題は 簡単に答えに 辿り着きましたが、
場合によっては かなりの時間や 労力が必要かも。

胸が大きいのが悩みなの。乳首は桜色だし。 · Answer

これが高校数学の問題ならyはそこまで大きくないはず。
yはxの約4倍。
110x-30y+(y-x)=1
y-x≡1 (mod10)
から試しにy-x=11とするとx=11/3≒4。
y=x+11=15とすると適する。

syotao · Answer

はい、最後のx≡4(mod.29)からのx＝4はかならず整数解になります。
まぐれではありません（笑）

ありものがたり · Answer

＞ 22x ≡ 1 (mod 29) や 22m = 1 + 7n から ｘ や ｍ や ｎ の検討をつける
＞ ことは、勘が働きやすいです。
＞ これなら、ユークリッドの互除法を使わなくとも整数解が見つけられる
＞ かもしれません

そこで止めずに、最後まで
109x - 29y = 1
→　22x ≡ 1 (mod 29)　→　22x = 1 + 29n
→　0 ≡ 1 + 7n (mod 22)　→　22m = 1 + 7n
→　m ≡ 1 (mod 7)
と書くと、これがユークリッド互除法であることが解りやすいかもしない。
22m = 1 + 7n よりも m ≡ 1 (mod 7) のほうが
更に解が見つけやすいだろうし。

書き方はともかく、各係数を見ると実際にやってる計算は
109 = 29・3 + 22,
29 = 22・1 + 7,
22 = 7・2 + 1,
7 = 1・7 + 0.　←割り切れたので、 1 が 109 と 29 の最大公約数
だから、内容は互除法そのものだ。

解の一例 m = 1 に気付いたら、
22m = 1 + 7n　から　n = 3,
22x = 1 + 29n　から　x = 4,
109x - 29y = 1　から　y = 15　を見つければ、
x = 4, y = 15 が 109x - 29y = 1 を満たすことが判る。

ここでは解の一例を見つけたいだけだから、最後までやらなくても
途中でカンが働けば、その時点でひとつの解に気付いてかまわない。
速さで言えば、そのほうが速い。

kairou · Answer

＞総当たり的な方法のように思えます。

NO2 です。　その通りです。
但し 109の倍数と 29の倍数の差が 1 ですから、
x の１桁目に +1 をすると y の１桁目になる筈です。
又 3x29<102<4x29 ですから、
 x=1 から x=9 迄行えば、答えが出てくるか、
見当が付くか どちらかになる可能性が高い、と考えました。

syotao · Answer

合同式が早い：
条件から109x≡1(mod.29)
109=29*4-7だから109≡-7(mod.29)
-7x≡1(mod.29)　4倍して
-28x≡4　一方28≡-1(mod.29)　だからx≡4(mod.29)ゆえ
x＝4としてこれをもとの方程式に入れてｙ＝15

sc348253 · Answer

y=(109x-1)/29
とし　Excel　または　calc   にて　x,y の価を求めれば
例えば　(x,y)=(4,15),(33,124),(62,233) など

ssawatake · Answer

7yじゃなかった

結局はユークリッドの互除法なんだけど、合同式を使う。
29で割った時の余りに着目する。
29yは余り0だから、109を7で割った時の余りが1になる筈。
109=(29×3+22)なので、29で割った余りは22

つまり22xを29で割った余りが1になる様なxを見つける。
22x≡1(mod29)を解く
x=4が見付かる(88÷29=3余り1)

以下略

ssawatake · Answer

結局はユークリッドの互除法なんだけど、合同式を使う。
29で割った時の余りに着目する。
7yは余り0だから、109を7で割った時の余りが1になる筈。
109=(29×3+22)なので、29で割った余りは22

つまり22xを29で割った余りが1になる様なxを見つける。
22x≡1(mod29)を解く
x=4が見付かる(88÷29=3余り1)

以下略

kairou · Answer

一般的には 合同式を使うのでは。（原理的には 互除法ですが。）
或いは モット原始的に x=1 → 109-1=29y 、
x=2 → 218-1=29y , ・・・と １つづつ 試してみるとか。

109x-29y=1 の整数解の見つけ方（互除法を使わず）

NO7 に対する 補足文に対して。

これが高校数学の問題ならyはそこまで大きくないはず。

はい、最後のx≡4(mod.29)からのx＝4はかならず整数解になります。

＞ 22x ≡ 1 (mod 29) や 22m = 1 + 7n から ｘ や ｍ や ｎ の検討をつける

＞総当たり的な方法のように思えます。

合同式が早い：

y=(109x-1)/29

7yじゃなかった

結局はユークリッドの互除法なんだけど、合同式を使う。

一般的には 合同式を使うのでは。

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

NO7 に対する補足文に対して。

＞ 22x ≡ 1 (mod 29) や 22m = 1 + 7n からｘやｍやｎの検討をつける

一般的には合同式を使うのでは。