pythonの逆元(数論逆数)

逆数は皆さんご存知でしょうaの逆数はbで、それではa× b = 1 a\times b=1 a×b=1. では、数論の逆数は?数論は基本的に型を取るのと同じで、同じく推測することができるでしょう型pの意義の下で、aの逆元はbで、aがあります× b ≡ 1 ( m o d   p ) a\times b\equiv 1(mod\space p) a×b≡1(mod p)すなわちa× b a\times b a×bは1であってもよいし、1+pであってもよいし、1+2 pであってもよい......注意:gcd(a,p)=1の場合にのみ解があり、すなわちaとpの相互質である.では、逆元はどうやって求めますか.1つ目:フェマは得意げに笑っている(•̀ ω •́ )ゞ✧费马小定理登场!!ゞpが素数であるときx p−1≡1(m o d p)x^{p−1}equiv 1(modspacep)xp−1≡1(mod p)では両側÷xdivx÷x,x p−2≡x−1(m o d p)x^{p−2}equivx^{−1}(modspacep)xp−2≡x−1(mod p)ではこれが容易になり,x p−2 m o d p−2 p x^{p−2}{p−2}x^p−2}x^{p−2}x^p−2}p)xp−2≡x−2≡x−1(mod p)を直接求めることが容易になり,x p p−space modspace p xp−2 mod pでよい.高速べき乗解で終わります.
2つ目:ユークリッドはフェマを蹴り返さなければならない.pが質量数でなければ、拡張ユークリッドを使わなければなりません.同余方程式の重さは変形aにある× b ≡ 1 ( m o d   p ) ⇒ a × b + p × k = 1 a\times b\equiv 1(mod\space p)\Rightarrow a\times b+p\times k = 1 a×b≡1(mod p)⇒a×b+p×k=1これは更に熟知したexgcdの(前提はgcd(a,p)=1)exgcdのあれらの事を理解していませんか?

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q


def inf(a,p):
    x, y, q = exgcd(a,p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p #