Eulersche phi Funktion

Aufrufe: 65     Aktiv: 17.09.2022 um 20:52

0

Bestimmtem Sie φ(323) wobei φ die Euler’sche Phi-Funktion ist. Geben Sie

hierzu die Definition der Funktion φ an. Hinweis: 323 ist das Produkt zweier

Primzahlen.


Habe auch recherchiert aber leider nichts gutes gefunden. Schreibe bald eine Prüfung, wäre nett, wenn mir einer helfen könnte.

Diese Frage melden
gefragt

Student, Punkte: -25

 
Kommentar schreiben
1 Antwort
-1
Hi frosan,

in deinem Fall weißt du, dass 323 in zwei Primfaktoren zerlegt werden kann. Für 323 sind diese 17 und 19.
Die Phi-Funktion ist nun definiert als Kardinalität der Menge aller Zahlen kleiner n, deren Primfaktoren, bis auf 1, disjunkt mit den Primfaktoren von n sind. Durch den Fakt, dass es nur zwei Primfaktoren gibt weißt du, dass es in der Menge $\{n \in \mathbb{N} | n \leq 323\}$ 19 Zahlen gibt die durch 17 teilbar sind und 17 Zahlen die durch 19 teilbar sind und diese somit mindestens einen Primfaktor mit 323 teilen. Daher kannst du mit $\phi(323) = 323 - 19 - 17 + 1$ die Lösung berechnen. Der $+1$ Term ist notwendig, da 323 sowohl durch 17 als auch durch 19 teilbar ist und so zwei mal gezählt wird und ausgeglichen werden muss.

Eine geschlossene Formel ist mit $\phi(n) = n \cdot \left( \prod_{p|n}(1- \frac{1}{p})\right)$ gegeben. Die Menge $\{p|n\}$ ist dabei die Menge der Primfaktoren von n.
Diese Antwort melden
geantwortet

Punkte: 5

 

Vielen Dank!   ─   frosan 17.09.2022 um 20:52

Kommentar schreiben