センター試験の一次不定方程式の問題をPythonで解いてみた。

　センター試験の一次不定方程式の問題をPythonで解いてみました。(^_^;

(1) 92x+197y= 1
(2) 92x+197y=10
　※整数x,yの組の中で、xの絶対値が最小のもの

　ちなみに、自力で解くとすれば、まず、問題の一次不定方程式の一組の整数解を見つけなければなりませんが、その見つけ方はこちらを参照して下さい。(^_^;
　一組の解が見つかったら、(1)は、一般に、次のようにして解きます。
　…①
　…②
①-②
　　ただし、a,bは互いに素
∴
∴
　また、(2)は、②の両辺を10倍して、
　
よって、が一組の解です。
　でも、これをこのまま解としたらダメでちゃんと(1)と同様にして、解をkの式で表して、k=-1,0,1を代入して、それらを比較してxの絶対値が最小のものを見つければならないようです。

● Bezout2.py

# coding: UTF-8
# Bezout2.py

def main():
    R = range(-200,200)
    D = [1,10]
    for d in D:
        ans = []
        min = float("inf")          # 最小値の初期値を∞にしてみた
        for x in R:
            for y in R:
                if 92*x+197*y==d:
                    if x*x< min:    # xの絶対値が最小のものを求める
                        ans = [x,y]
                        min = x*x

        print('(%d) %s'%(D.index(d)+1,ans))

if __name__ == '__main__':
    main()

●実行結果

(1) [15, -7]
(2) [-47, 22]

　去年の4月に、「ユークリッドの互除法を用いる一次不定方程式の解の見つけ方の裏ワザ」をYoutubeで見つけましたが、これをPythonでやってみました。(^_^;

● EuclidsAlgo1.py

# coding: UTF-8
# EuclidsAlgo1.py

def main():
    R = [197,92]            # 降順
    R.sort(); R.reverse()   # 念の為
    Q = [0]
    a,b = R[0],R[1]
    while b!=0:
        Q.append(a//b)
        R.append(a%b)
        a,b = b, a%b

    q = list(reversed(Q))
    n = len(Q)
    c = [0,1]+[0]*(n-2)
    for i in range(2,n):
        c[i] = q[i-1]*c[i-1]+c[i-2]
    C = list(reversed(c))

    s = t = ''
    if R[0]*C[1]> R[1]*C[0]: s = '(-)'
    else:                    t = '(-)'

    print("  R   Q   C  ")
    print("-------------")
    print("%3d   X %3d --> %d %s"%(R[0],     C[0],R[1]*C[0],s))
    print("%3d %3d %3d --> %d %s"%(R[1],Q[1],C[1],R[0]*C[1],t))
    for i in range(2,n-1):
        print("%3d %3d %3d"%(R[i],Q[i],C[i]))
    print("%3d  -->%3d"%(R[n-1],C[n-1]))

if __name__ == '__main__':
    main()

●実行結果

  R   Q   C
-------------
197   X  15 --> 1380
 92   2   7 --> 1379 (-)
 13   7   1
  1  -->  0

※参考URL
●大学入試センター試験｜解答速報2016｜予備校の東進
●ユークリッドの互除法（その②）（一次不定方程式と裏ワザ）
●質問の一次不定方程式の一組の整数解をPythonで求めてみた。