Beweis zu Euler phi -Funktion: ϕ(n)≤n.

Question

Aufgabe:

Zeige dass ϕ(n) ≤ n gilt.

Problem/Ansatz:

Aus der Zahlentheorie weiß ich bereit, dass ich ϕ(n) in Primfaktoren zerlegen könnte . Leider weiß ich nicht wie mir dies bei dieser Aufgabe weiterhilft. Würde mich über Hilfe freuen.

Answer 1

ϕ(n) ist doch die Anzahl der zu n teilerfremden

Zahlen im Bereich von 1 bis n.

Dort gibt es doch überhaupt nur n Zahlen,

also ist das Ergebnis sicherlich kleiner oder gleich n.