Problem mit modularer multiplikativer Inverse.

Question

Ich versuche mein Bestes, um eine meiner Vorbereitungsübungen zu lösen. Ich habe eine These, die richtig zu sein scheint (ich habe sie auf kleine Zahlen überprüft), aber ich kann sie nicht beweisen .... Hier ist es also:$x \perp n $ und $x+1 \perp n.\, $ Lassen $\,x' = x^{-1}\bmod n.\,$ Beweise das $ x' \perp n $ und $ x' + 1 \perp n $. Erster Teil mit$ x' \perp n $ist einfach, aber zweitens kann ich nicht beweisen. Danke für jede Hilfe!

Answer 1

Während dies durch Manipulation von Bezout-Gleichungen beweisbar ist, verdeckt dies die arithmetische Struktur im Kern der Sache - das$\color{#c00}{\text{divisors}}\!$ $\!\color{#0a0}{\text{ of invertibles remain invertible}}$. Lassen Sie uns das in den Vordergrund rücken.

Rückruf von Bezout dass$\,a$ ist invertierbar $\!\bmod n\iff a\,$ ist Koprime zu $n.\,$ Wenn Sie dies unten anwenden, erhalten Sie

$\!\bmod n\!:\ a$ ist invertierbar $\Rightarrow aa^{-1}\equiv 1$ damit $a^{-1}$ ist invertierbar (mit invers $\equiv a)$ damit $a^{-1}$ ist Koprime zu $n$

Beachten Sie außerdem, wenn $\,a \equiv \color{#c00}b\,c\,$ dann $\,1 \equiv aa^{-1} \equiv b(ca^{-1})$ damit $\,\color{#c00}b\,$ ist $\color{#0a0}{\text{also invertible}}$ (mit invers $ca')$.

Also umkehrbar $\ x+1 \equiv (\color{#c00}{1+x^{-1}})x\,\Longrightarrow\,$ invertierbar $\,\color{#c00}{1+x^{-1}}.\,$ Beide Behauptungen sind auf diese Weise offensichtlich.

Anmerkung $ $ Der erste Anspruch kann auch auf diese Weise abgeleitet werden, dh $\,aa^{-1}\equiv 1\,$ damit $\,a^{-1}$ ist ein Teiler des Invertierbaren $1$ so bleibt es invertierbar.

Somit wird der Satz von Invertibles unter Teilern und Produkt geschlossen. Eine solche algebraische Struktur ist als gesättigtes Monoid bekannt und erweist sich in der Zahlentheorie als sehr nützlich.

Answer 2

Bezeichnen wir $a=x \ mod^{-1} \ n$. Es existiert$b$ so dass $ax + bn = 1$. Dies ist von Bezout klar, dass$gcd(a,n)=1$.

Für den zweiten Teil existiert nun nach Hypothese $c,d$ so dass $c(x+1)+dn=1$. Dann hat man$$ (a+1)cx + (bc+d)n = c(ax + bn) + cx + dn = c + 1-c = 1$$ damit $gcd(a+1,n)=1$.