A set of integers that satisfies ax + by = 1.

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

A set of integers that satisfies ax + by = 1.
[Python] A program that creates a two-dimensional array by combining integers
Divide a set of integers into cosets in one shot
Construction of a neural network that reproduces XOR by Z3
A set of script files that do wordcloud in Python3
Implementation of a model that predicts the exchange rate (dollar-yen rate) by machine learning
A program that sends a fixed amount of mail at a specified time by Python
Combinatorial optimization --Typical problem-- Partition of a set problem
A memorandum of extraction by python bs4 request
A verification of AWS SDK performance by language
Get a list of Qiita likes by scraping
How to create a property of relations that can be prefetch_related by specific conditions
[Linux] A list of Linux commands that beginners should know
A story that reduces the effort of operation / maintenance
[Python] A program that counts the number of valleys
A script that takes a snapshot of an EBS volume
(Python) Treat integer values as a set of flags
[GoLang] Set a space at the beginning of the comment
Add a list of numpy library functions little by little --a
Make a BOT that shortens the URL of Discord
# Function that returns the character code of a string
Python that merges a lot of excel into one excel
A story that struggled with the common set HTTP_PROXY = ~
A shell program that becomes aho in multiples of 3
A script that outputs a list of SoftLayer portal users
Generate that shape of the bottom of a PET bottle
Super simple: A collection of shells that output dates
Group by consecutive elements of a list in Python
A story that analyzed the delivery of Nico Nama.
[Python] A program that compares the positions of kangaroos.
A library that monitors the life and death of other machines by pinging from Python
An example of a mechanism that returns a prediction by HTTP from the result of machine learning