Dans la question 6 des 58e Jeux Olympiques, la question de la théorie élémentaire des nombres entiers, que l'on peut appeler tradition, a été posée.
Dans ce problème, le fait qu '"il y a des entiers x et y qui satisfont ax + by = 1 pour les entiers mutuellement premiers a et b" est utilisé comme une connaissance courante dans le sens commun. Ici, je rapporterai le résultat de la mise en œuvre du bon sens dans le sens commun avec python.
python
print("Entrez deux entiers positifs qui s'excluent mutuellement.")
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=Les entiers x et y qui satisfont 1"+str(a**(n-1))+"Quand"+str(-m)+"est.")
La théorie elle-même est le théorème d'Euler introduit plus tôt. https://qiita.com/naoya_suzuki/items/5490a1099dee8ad7065e
Si vous essayez a = 6 et b = 11, vous devriez voir "Les entiers x et y qui satisfont 6x + 11y = 1 sont 10077696 et -5496925." C'est un nombre étonnamment grand, donc vous ne pouvez pas le trouver même si vous le cherchez sans faire de politique du tout. (; ^ _ ^ A
Post-scriptum: Si vous y réfléchissez, vous pouvez comprendre intuitivement x = 2 et y = -1.
Recommended Posts