Zeige, dass der Satz von Fermat aus dem Satz von Euler geschlussfolgert

Question

Die Eulersche Phi-Funktion ist wie folgt definiert:
ϕ(n) = {x ∈ N+ | x ≤ n ∧ ggT(x, n) = 1}

Der Satz von Euler lautet nun:
Seien x, n ∈ N+ teilerfremd, dann gilt x^ϕ(n) ≡ 1 mod n.

Zeige, dass der Satz von Fermat aus dem Satz von Euler geschlussfolgert
werden kann.

Comments

Schon was versucht? Wo bist du stuck?

Was ist \(\Phi(p)\) für eine Primzahl \(p\)?

---

Habe verzweifelt rumprobiert ,aber bin ganz schlecht bei beweisen. Habe noch nicht das Verständnis dafür entwickelt.

Zu deiner Frage sollte es P=p-1 sein soweit ich weiß

Answer 1

Fermat ist doch wohl: \( a^p ≡ a   (\mod p)  \) für alle a∈ℤ und p Primzahl.

oder anders geschrieben   \( a^{p-1} ≡ 1    (\mod p)  \) für alle a∈ℤ und p Primzahl.

Nun sind ja sicherlich a und 1 teilerfremd und damit liefert Euler jedenfalls für a∈ N+

\( a^{ \Phi(p)} ≡ 1  ( \mod p )\)

Und wegen \( \Phi(p)  = p - 1 \)  für Primzahlen, hast du wie gewünscht :

\( a^{p-1} ≡ 1    (\mod p)  \)

Comments

oder anders geschrieben   \( a^{p-1} ≡ 1    (\mod p)  \) für alle a∈ℤ und p Primzahl.

Im Fall p|a gilt das eben gerade nicht.

Nun sind ja sicherlich a und 1 teilerfremd und damit liefert Euler jedenfalls für a∈ N+

Nicht a und 1 müssen teilerfremd sein um Euler anwenden zu können, sondern a und p.

Wenn man Fermat in der verallgemeinerten Darstellung folgern möchte macht man eine Fallunterscheidung \(p|a\) und \(p\nmid a\)