互いに素な整数a,bに対しax+by=1を満たす整数x,yの組。

第58回数学オリンピックの問６では、伝統とも言うべき初等整数論の問題が出題されました。

その問題では「互いに素な整数a,bに対しax+by=1を満たす整数x,yが存在する」という事実が常識中の常識として使われます。
ここではその常識中の常識をpythonで実装してみた結果を報告します。

print("互いに素な正の整数を２つ入力して下さい。")
a, b= map(int, input().split())
n = 1
r = a**n % b
#print(r)
while r > 1:
    n = n + 1
    r = a**n % b
    #print(r)
m = a**n // b
print(str(a)+"x+"+str(b)+"y=1を満たす整数xとyは"+str(a**(n-1))+"と"+str(-m)+"です。")

理屈自体は、以前紹介したオイラーの定理です。
https://qiita.com/naoya_suzuki/items/5490a1099dee8ad7065e

試しにa=6,b=11としてみると「6x+11y=1を満たす整数xとyは10077696と-5496925です。」と出てくるはずです。意外と大きな数ですので全く方針を立てずに探しても見つからないですね。(;^_^A

追記：
と思ったらx=2,y=-1は直感で分かりますね。