質問の一次不定方程式の一組の整数解をPythonで求めてみました。(^_^;
一次不定方程式には整数解がいくつもあるので、二乗の和が一番小さいものを求めることにしました。
ちなみに、この一次不定方程式には名前があって、ベズーの等式というそうです。
● Bezout1.py
# coding: UTF-8 # Bezout1.py ans = [] # 最小の組が複数ある場合の対策 min = float("inf") # 最小値の初期値を∞にしてみた r = range(-100,100) for x in r: for y in r: if 24*x+19*y==1: if x*x+y*y< min: # 二乗の和が一番小さいものを求める if len(ans)!=0: ans.pop() ans.append([x,y]) min = x*x+y*y elif x*x+y*y==min: ans.append([x,y]) print(ans)
●実行結果
[[4, -5]]
ちなみに、数学的には次のようにして求めます。
＞ 24x+19y=1
＞ これを計算すると
＞ 24=19×1+5
∴
∴
とおくと、
で、
＞ 19=5×3+4
∴
∴
とおくと、
で、
＞ 5=4×1+1
∴
∴
とおくと、
で、
＞ 式変形していきます。
どっちかの係数が1になれば、それを1、他方を0とすれば整数解の一つが求まるので、
これらと(3)から、
これらと(2)から、
これらと(1)から、
質問のユークリッドの互除法を使った計算では、これを数字だけで機械的に計算しているのだと思われますが、分かりやすくするために、次のようにするのはどうでしょうか。(^_^;
残す数字を［］括弧で、互除法の余りの数字を{}括弧でくくっておいて、この余りの部分を下から順に代入して消去していきます。ここで、括弧は四角や丸で囲んでもいいのですが、書きにくいので括弧でくくることにしました。(^_^;
ちなみに、下から代入していくのは、代入した後、式を整理すると、代入を1回で済ませることが出来るからです。それから、式変形の方針としては、[]括弧で括った数字は最後まで残し、{}括弧で括った数字は'文字'(式)のように代入法で消去していきますが、代入して消去する場合以外は残す(壊さない)ということにも注意しましょう。
24=19×1+5 ∴ {5}=[24]-[19]×1
19=5×3+4 ∴ {4}=[19]-{5}×3
5=4×1+1 ∴ [1]={5}-{4}×1
∴以上より、
[1]={5}-{4}×1 ← これに{4}=[19]-{5}×3を代入
={5}-([19]-3{5})×1 ← これを整理すると
=4{5}-[19] ← これに{5}=[24]-[19]×1を代入
=4([24]-[19]×1)-[19] ← これを整理すると
=4[24]-5[19]
=24(4)+19(-5) 数字を文字的に扱うとこがユニークですが、分かりにくければ、実際に文字で置いてみるのもいいかも知れません。
M=24,N=19,p=5,q=4と置くと、
24=19×1+5 ∴ {5}=[24]-[19]×1 ∴ p=M-N×1
19=5×3+4 ∴ {4}=[19]-{5}×3 ∴ q=N-p×3
5=4×1+1 ∴ [1]={5}-{4}×1 ∴ 1=p-q×1
∴以上より、
1 =p-q×1 ← これにq=N-p×3を代入
=p-(N-p×3) ← これを整理すると
=4p-N ← これにp=M-N×1を代入
=4(M-N×1)-N ← これを整理すると
=4M-5N
=M(4)+N(-5)
=24(4)+19(-5)P.S.
ちょっと、Youtubeの動画を検索してみたら、いいの(裏ワザ)が見つかったので参考URL(上から５番目)にはっておきました。o(^-^)o
この問題に動画の方法を使えば、次のようになります。
R Q C ------------- 24 X 5 --> 95 (-) 19 1 4 --> 96 5 3 1 4 1 1 1 --> 0
※参考URL
●5. データ構造 ─ Python 2.7ja1 documentation
●Pythonでは無限大と数値の比較ができる - anon21's Blog
●ディオファントス方程式
●ユークリッドの互除法の証明と不定方程式 | 高校数学の美しい物語
●ユークリッドの互除法（その②）（一次不定方程式と裏ワザ）
●ディオファントス方程式の質問を十進BASICで解いてみた。
●知恵袋の1次不定方程式の整数解の問題をJavaで解いてみた。
●センター試験の一次不定方程式の問題をPythonで解いてみた。 - rscのブログ
