0 Daumen
370 Aufrufe

Aufgabe:

Sei n ∈ N und p eine Primzahl. Für die Eulersche Funktion gilt: φ(p^n) = p^n - p^n-1

(a) Verifizieren Sie die Formel für n = 3 und p = 3.

(b) Beweisen Sie die Formel im allgemeinen Fall.

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Verifizierung für n = 3 und p = 3

Um die gegebene Formel \(\varphi(p^n) = p^n - p^{n-1}\) zu verifizieren, setzen wir \(n = 3\) und \(p = 3\) ein:

\(\varphi(3^3) = 3^3 - 3^{3-1}\)

Berechne zunächst die Exponenten:

\(3^3 = 27\)

\(3^{3-1} = 3^2 = 9\)

Also, \(\varphi(3^3) = 27 - 9 = 18\).

Daher ist, für \(n = 3\) und \(p = 3\), der Wert von \(\varphi(3^3) = 18\) verifiziert.

Beweis der Formel im allgemeinen Fall

Um zu zeigen, dass für eine Primzahl \(p\) und eine positive ganze Zahl \(n\), die Formel \(\varphi(p^n) = p^n - p^{n-1}\) wahr ist, verwenden wir die Eigenschaften der Eulerschen Phi-Funktion und die Definition einer Primzahl.

Die Eulersche Phi-Funktion \(\varphi(m)\) gibt die Anzahl der positiven ganzen Zahlen an, die zu \(m\) relativ prim sind und kleiner oder gleich \(m\) sind. Für eine Primzahl \(p\) und ihre Potenz \(p^n\), sind die Zahlen, die nicht relativ zu \(p^n\) prim sind, genau die Vielfachen von \(p\) (d.h., \(p, 2p, 3p, \ldots, p^{n-1}p\)). Es gibt genau \(p^{n-1}\) solche Zahlen unter den Zahlen \(1, 2, \ldots, p^n\).

Da in der Menge \(\{1, 2, \ldots, p^n\}\) insgesamt \(p^n\) Zahlen enthalten sind, und \(p^{n-1}\) davon nicht relativ prim zu \(p^n\) sind (weil sie Vielfache von \(p\) sind), sind also genau \(p^n - p^{n-1}\) Zahlen relativ prim zu \(p^n\).

Deshalb gilt allgemein die Formel: \(\varphi(p^n) = p^n - p^{n-1}\).

Dieser Beweis zeigt, dass die Formel \(\varphi(p^n) = p^n - p^{n-1}\) für jede Primzahl \(p\) und jede natürliche Zahl \(n\) gültig ist.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community