Euler'sche Phi-Funktion

Die Euler’sche Phi-Funktion (Euler’sche φ MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGcbaGaeqOXdOgaaa@3EAA@ –Funktion) ist eine Funktion, deren Definitionsmenge die natürlichen Zahlen sind. Der Funktionswert φ ( n ) MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGcbaGaeqOXdOMaaiikaiaad6gacaGGPaaaaa@40F6@ einer natürlichen Zahl n ist dabei jeweils die Anzahl der zu n teilerfremden natürlichen Zahlen, die nicht größer als n sind. Ein Funktionswert φ ( n ) MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGcbaGaeqOXdOMaaiikaiaad6gacaGGPaaaaa@40F6@ lässt sich folgendermaßen berechnen: Man schreibt n als Produkt von verschiedenen Primzahlen: n = p 1 h 1 ⋅ p 2