Pythonで不定方程式を計算する

不定方程式は大学センター試験の数学の問題の常連でした。先日行われた新しい大学入学共通テストでも出題され、引き続き必須の項目となっています。この中で2016年に出題された方程式はxとyの組合せを見付けるのが大変でした。そこで、この計算をPythonでできるようにしてみます。

問題は次の式を満たす整数x,yの組の中でxが最小のものを求める問題です。
$92x+197y=1$

def xgcd(a,b):
    prevx, nextx = 1, 0
    prevy, nexty = 0, 1
    while b:
        quotient = a//b
        nextx, prevx = prevx - quotient * nextx, nextx
        nexty, prevy = prevy - quotient * nexty, nexty
        a, b = b, a % b
        print(a,b)
    return prevx, prevy,a

xgcd(92,197)

197 92
92 13
13 1
1 0
(15, -7, 1)

となり、$x=15,y=-7$となります。これにはユークリッドの互除法が活用されているので、拡張ユークリッドの互除法(Extended-Euclidean-Algorithm)といわれています。これは、とても活用範囲が広いので、SymPYに関数が用意されています。

import sympy
sympy.gcdex(92,197)

(15, -7, 1)

これは掘り下げる価値がありそうです。