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

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 …

No.9 回答者： syotao 回答日時： 2024/10/14 22:09

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

まぐれではありません（笑）

No.8 回答者： ありものがたり 回答日時： 2024/10/14 21:05

＞ 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 を満たすことが判る。

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

No.7 回答者： kairou 回答日時： 2024/10/14 20:17

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

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

No.6 回答者： syotao 回答日時： 2024/10/14 15:20

合同式が早い：

条件から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

この回答へのお礼

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

合同式は便利ですね！xの検討がつきやすくなります。
このｘ＝４は必ず整数解になりますか？それとも、今回はたまたま整数解になって運がよい、という展開でしょうか？

お礼日時：2024/10/14 19:07

No.5 回答者： sc348253 回答日時： 2024/10/14 01:37

y=(109x-1)/29

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

この回答へのお礼

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

本質的には、総当たりで探すという解釈で合っていますか？

お礼日時：2024/10/14 19:07

No.4 回答者： ssawatake 回答日時： 2024/10/13 19:35

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)

以下略

この回答へのお礼

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

合同式は便利ですね！xの検討がつきやすくなります。
> 22x≡1(mod29)を解く
> x=4が見付かる(88÷29=3余り1)
このｘ＝４は必ず整数解になりますか？それとも、今回はたまたま整数解になって運がよい、という展開でしょうか？

お礼日時：2024/10/14 19:05

No.3 回答者： ssawatake 回答日時： 2024/10/13 19:34

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

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)

以下略

この回答へのお礼

（次の回答へのお礼いたします）

お礼日時：2024/10/14 19:03

No.2 回答者： kairou 回答日時： 2024/10/13 18:40

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

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

この回答へのお礼

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

これだといずれかは解が見つかりますが、総当たり的な方法のように思えます。それとも、もっと深い意味はありますか？

お礼日時：2024/10/14 19:02

No.1 回答者： ありものがたり 回答日時： 2024/10/13 18:28

カンで見つけるのが早いっちゃ早いかな。

解を見つけるための操作手順としては、
事実上ユークリッド互除法でしかないものを
別の方法であるかのように書いて見せる方法は
いくつか知られている。

109x - 29y = 1 を mod 29 へ移行して
22x ≡ 1 (mod 29) から 22x = 1 + 29n.
これを mod 22 へ移行して
0 ≡ 1 + 7n (mod 22) から 22m = 1 + 7n.
とやってくとか、

109/29 の連分数展開を使ったり、
その連分数展開に行列積を使う方法とか。

どれも皆、ユークリッド互除法の計算手段
なんだけどね。

この回答へのお礼

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

★22x ≡ 1 (mod 29)から、候補としてｘ＝４は思いつきやすいかもしれません。ところで、ここでの★はｘが満たすべき必要条件であるため、ｘ＝４が解とは限らない（たまたまｘ＝４が解になっているだけ）という解釈であっているでしょうか。

22x ≡ 1 (mod 29)　や　22m = 1 + 7n　から　ｘ や ｍ や ｎ の検討をつけることは、勘が働きやすいです。

これなら、ユークリッドの互除法を使わなくとも整数解が見つけられるかもしれません…というのは未熟で

>事実上ユークリッド互除法でしかないものを別の方法であるかのように書いて見せる

なのですか？

お礼日時：2024/10/14 19:01