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

1 Beispiele

2 Berechnung

2.1 Primzahlen
2.2 Potenzen von Primzahlen
2.3 Multiplikativität
2.4 Zusammengesetzte Zahlen

3 Bedeutung der φ-Funktion:

4 Weblinks

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 ⁴) = 2 ⁴ - 2 ³ = 16 - 8 = 8 φ(16) = φ(2 ⁴) = 2 ³ * (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.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

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