Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 29. Juli 2014 

Eulersche φ-Funktion


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Eulersche Phi-Funktion ist eine zahlentheoretische Funktion . Sie ordnet jeder natürlichen Zahl n die Anzahl der natürlichen Zahlen a von 1 bis n zu die zu n teilerfremd sind (also ggT ( a n ) = 1).

Sie ist benannt nach Leonhard Euler und wird mit dem griechischen Buchstaben ( Phi ) bezeichnet.

Inhaltsverzeichnis

Beispiele

Die Zahl 6 ist zu 2 zwischen 1 und 6 teilerfremd (1 und also ist φ(6) = 2.
Die Zahl 13 ist als Primzahl zu den 12 Zahlen von 1 12 teilerfremd also ist φ(13) = 12.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
φ( n ) 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6

Berechnung


Primzahlen

Da alle Primzahlen p nur durch 1 und sich selbst teilbar sind sind sie sicher zu den 1 bis p -1 teilerfremd daher ist φ( p ) = p -1

Potenzen von Primzahlen

Eine Zahl p α (wobei p ein Primzahl und α ≥ 1 ist nur zu Vielfachen von p nicht teilerfremd. Es gibt p α-1 Vielfache von p die kleiner oder gleich p α sind (1* p 2* p ... p α-1 * p ) daher gilt:

<math>\varphi(p^\alpha) = p^\alpha - p^{\alpha-1} = p^{\alpha-1}(p-1)</math>

Beispiel: φ(16) = φ( 2 4 ) = 2 4 - 2 3 = 16 - 8 = 8 φ(16) = φ(2 4 ) = 2 3 * (2 - 1) = 8 1 = 8.

Multiplikativität

Die φ-Funktion ist multiplikativ das heißt ggt(m n) = 1 gilt:

<math>\varphi(mn) = \varphi(m)\varphi(n)</math>

Beispiel: φ(18) = φ(2) * φ(9) 1 * 6 = 6.

Zusammengesetzte Zahlen

Die Berechnung von φ( n ) für zusammengesetzte n ergibt sich aus der Multiplikativität. Hat n die kanonische Darstellung

<math>n = \prod_{p\mid n} p^{\alpha_p} </math> (p Primzahl)
so gilt
<math>\varphi(n) = \prod_{p\mid n} p^{\alpha_p-1}(p-1) = n n}(1-\frac{1}{p})</math>

Beispiel: φ(72) = φ(2³*3²) = 2 3-1 (2-1) * 3 2-1 (3-1) = 2² * 1 * 3 2 = 24.

Bedeutung der φ-Funktion:

Eine der wichtigsten Anwendungen findet die im Satz von Fermat-Euler :

Wenn zwei ganze Zahlen a und m ≥ 2 teilerfremd sind gilt: m teilt ( a φ( m ) - 1) oder anders formuliert:

<math>a^{\varphi(m)} \equiv 1 \pmod m</math>
Ein Spezialfall (für m ist Primzahl) dieses Satzes ist der Kleine Fermatsche Satz : p teilt ( a p-1 - 1) bzw.
<math>a^{p-1} \equiv 1 \pmod p</math>
Der Satz von Fermat-Euler findet u.a. bei der Generierung von Schlüsseln für das RSA -Verfahren in der Kryptographie .

Weblinks



Bücher zum Thema Eulersche φ-Funktion

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Eulersche_Phi-Funktion.html">Eulersche φ-Funktion </a>