In Question 6 of the 58th Mathematical Olympiad, the question of elementary number theory, which can be called tradition, was asked.
In that problem, the fact that "there are integers x and y that satisfy ax + by = 1 for relatively prime integers a and b" is used as common sense in common sense. Here, I will report the result of implementing the common sense in the common sense with python.
python
print("Enter two positive integers that are relatively prime.")
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=The integers x and y that satisfy 1 are"+str(a**(n-1))+"When"+str(-m)+"is.")
The theory itself is Euler's theorem introduced earlier. https://qiita.com/naoya_suzuki/items/5490a1099dee8ad7065e
If you try a = 6 and b = 11, you should see "The integers x and y that satisfy 6x + 11y = 1 are 10077696 and -5496925." It's a surprisingly large number, so you can't find it even if you look for it without making a policy at all. (; ^ _ ^ A
Postscript: If you think about it, you can intuitively understand x = 2 and y = -1.
Recommended Posts