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.11 ベストアンサー 回答者： kairou 回答日時： 2024/10/19 16:12

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 が 題意を満足することが分かります。

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

この回答へのお礼

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

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

１桁目に注目すれば
109x-29y=1 について、9x と 9y の差の１桁目が 1 になることと、
9の倍数の1の位が順に1ずつ減っていく性質から言えると理解することができました。

> 又 29x3<109<29x4 ですから、１桁目だけを考えれば、
> 3x<y<4x ; y=x+1 を満たす 整数の筈です。　←★
>（ごめんなさい 102 は ミスタイプでした。）

★の２つの性質を満たす x,y を探せばよいということですね。

>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 が 題意を満足することが分かります。

x=5の時は 15<y<20 で y=16 が該当しますが、
109/29≒3.75 を考えると(x,y)=(5,16)は不適

x=6の時は 18<y<24 で y=17 が不適
x=7の時は 21<y<28 で y=18 が不適
x=8の時は 24<y<32 で y=29 が該当しますが、
不定方程式を満たさない…

などと自分なりに考えることができました。
(4,15)で該当することはラッキーに思えてきました。

>「互除法を使わずに解に迫る方法」と言う事ですから、
>無理やり考えた結果です。

それでも、このように考えを広めることで、視野が広がるような気がします。
何よりも、「x：y＝29：109 の比の値を意識すること」は、はユークリッドの互除法で解けることに安心していては忘れてしまいます。
ありがとうございました。

お礼日時：2024/10/19 16:46

No.10 回答者： 胸が大きいのが悩みなの。乳首は桜色だし。 回答日時： 2024/10/15 21:25

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

yはxの約4倍。
110x-30y+(y-x)=1
y-x≡1 (mod10)
から試しにy-x=11とするとx=11/3≒4。
y=x+11=15とすると適する。

この回答へのお礼

回答ありがとうございます。はじめて見たとき、面白い解き方だと感じて胸が高まりました。それから、あれこれ考えています。


たとえば　531x - 47y = 1 ★について
531÷47=11.29…　より、y≒11x …　などとして、
同じ方法で特殊解を見つけることはできるでしょうか。
自分なりに考えているのですが、なかなかうまくいきません。

お礼日時：2024/10/18 22:52

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

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

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

この回答へのお礼

解答ありがとうございます。
x≡4 (mod.29)を満たす任意のxについて
-28x≡4 (mod.29)
-7x≡1 (mod.29)
22x≡1 (mod.29)
109x≡1 (mod.29)
よって、ある整数yが存在して 109x-1=29y
と逆に辿ることができました。
ここは納得できました。

お礼日時：2024/10/18 22:39

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

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

この回答へのお礼

> 途中でカンが働けば、その時点でひとつの解に気付いてかまわない。
互除法によって特殊解が見つかりますが、途中で気づくにはそれでよいということですね。互除法については、「必ず見つかる」というアルゴリズムにも価値があるわけですが、このQAでは、極力互除法によらない方法を模索しています。

お礼日時：2024/10/18 22:07

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

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

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

この回答へのお礼

> 但し 109の倍数と 29の倍数の差が 1 ですから、
> x の１桁目に +1 をすると y の１桁目になる筈です。
これはなぜですか？このことを「なるほど！」と簡単に理解することはできますか？かなり考えてx-y≡1 (mod 10)だからか！と思いましたが、もっと簡単に理解できますか？

>又 3x29<102<4x29
この102は何を意味していますか？

>又 3x29<102<4x29 ですから、
>x=1 から x=9 迄行えば、答えが出てくるか、
>見当が付くか どちらかになる可能性が高い、と考えました。
この部分の「ですから、」の部分がよく分からずにいます。

頭が悪くてすみません！

お礼日時：2024/10/18 22:04

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