Euler & Inversenbildung

Question

Aufgabe:

Berechnen Sie das multiplikative Inverse von 7 in ℤ16, indem Sie den Satz von Euler Fermat verwenden.

Problem/Ansatz:

Für teilerfremde Zahlen m , n ∈ ℕ mit n > 1 gilt:

m^φ(n) mod  n = 1

----------------------------------------------------------------------------

Ist das der richtige Ansatz? Wenn ja:
Was ist m, was ist n, durch was muss ich dann modulo rechnen?

Wenn nein, bitte ein Hinweis, womit ich anfange, hab das nicht so recht verstanden.

Danke :)

Answer 1

Hallo Aryn,

$$m^{\varphi(n)} \equiv 1 \mod n$$Ist das der richtige Ansatz? Wenn ja:
Was ist m, was ist n, durch was muss ich dann modulo rechnen?

Das ist das, was der Satz von Euler-Fermat besagt. Das \(n\) ist hier die 16, da Du Dich im \(\mathbb{Z}_{16}\) bewegst. Das \(m\) kann jede beliebige Zahl sein. Und \(\varphi(n)\) ist die Eulersche Phi-Funktion, die angibt, wie viele teilerfremde Zahlen zu \(n\) existieren, die nicht größer als \(n\) sind. $$\varphi(16) = 8$$da alle ungeraden Zahlen unter 16 zu 16 teilerfremd sind.

Die multiplikative Inverse zu \(7\) im \(\mathbb{Z}_{16}\) ist die Zahl \(x\), für die gilt$$7 \cdot x \equiv 1 \mod 16$$Dazu forme ich die Gleichung oben ein wenig um (\(n=16\))$$m \cdot m^{\varphi(16)-1} \equiv 1 \mod 16$$und setze für \(m\) die \(7\) ein$$7 \cdot \underbrace{7^{\varphi(16)-1}}_{=x} \equiv 1 \mod 16$$Also ist$$\begin{aligned} x &\equiv 7^{8-1} &&\mod 16 \\ x &\equiv 7 &&\mod 16\end{aligned}$$Gruß Werner