Lade Inhalt...

Primzahlen - ein Überblick

Ausarbeitung 2012 15 Seiten

Mathematik - Zahlentheorie

Leseprobe

Inhaltsverzeichnis

1. Einleitung

2. Was ist eine Primzahl?
1. Wortbedeutung
2. Definition

3. Prime und zusammengesetzte Zahlen
1. Primfaktorzerlegung
2. ggT, kgV und mehr
3. Warum 1 keine Primzahl ist

4. Wieviele Primzahlen gibt es?
1. Unendlichkeitsbeweis nach Euklid
2. Verteilung der Primzahlen

5. Primzahlkonstellationen
1. Allgemeines
2. Fermat'sche Primzahlen .

6. Wie lassen sich Primzahlen bestimmen?
1. ieb des Eratosthenes
2. ieb von Atkin
3. Probedivision
4. Kleiner Fermat

7. Primzahlen in der Kryptographie
1. Grundidee von RA
2. Der offentliche chlussel
3. Chiffrieren und Dechiffrieren
4. Der private chlussel

8. chlusswort

9. Literaturverzeichnis

1. Einleitung

Primzahlen sind geheimnisvolle, seltsame Zahlen und sorgen schon seit je her fur groEe Fragezeichen in den Kopfen von Mathematikern und Mathematikerinnen.

Aber was hat es mit jenen Sonderlingen eigentlich auf sich? Was fur eine Rolle spielen diese Zahlen, wo sie doch auf den ersten Blick ihren Verwandten und Nachbarn, den naturlichen Zahlen, in allem gleich sind? Nun, eben diese Antworten, oder zumindest ein tieferes Verstandnis innerhalb dieses groEen Mysteriums der Primzahlen, ist Ziel dieser Facharbeit. Sie ladt dazu ein, den Ratseln der Mathematik auf die Spur zu kommen und versucht, ein weiteres Licht im so abstrakten Raume aufleuchten zu lassen.

Im Folgenden wird sowohl auf die Eigenschaften der Primzahlen eingegangen als auch ihre grundlegende Bedeutung in Bezug auf die elementare Mathematik deutlich gemacht. Des Weiteren behandelt diese Ausarbeitung mehrere deterministische Verfahren, um auf Primzahlen bzw. Primalitat1 zu schlieEen und erlautert einen Teil der modernen Kryptographie, welcher durch Primzahlen erst moglich wird.

Abbildung in dieser Leseprobe nicht enthalten

2. Was ist eine Primzahl?

2.1 Wortbedeutung

Der Ursprung des Wortes ,,Primzahl“ liegt im lateinischen Begriff „numerus primus“, was „die erste Zahl“ oder „Anfangszahl“ bedeutet. Etymologisch gesehen sind Primzahlen also die Grundbausteine der Mathematik, die Zahlen, mit denen alles beginnt.

2.2 Definition

Primzahlen sind naturliche Zahlen groEer als 1 , welche nur durch 1 und sich selbst restlos teilbar sind. 2 ist die kleinste und einzig gerade Primzahl, da jede groEere gerade Zahl als ein Vielfaches von ihr mindestens 3 Teiler besitzt. Formal haben Primzahlen p>2 also die Form 2k + 1, k e N + , die ersten zehnlauten: 2,3,5,7,11,13,17,19,23 und 29 .

Primzahlen, die direkt aufeinanderfolgen, nennt man Primzahlzwillinge, -drillinge; (11,13,17,19) bildetsogareinPrimzahlvierling.

Der Einfachheit halber sei in dieser Facharbeit P = {pelN| p prim} als die Primzahlmenge definiert.

3. Prime und zusammengesetzte Zahlen

So, wie die Menge der naturlichen Zahlen N nach jenen geraden und ungeraden, also durch 2 teilbaren und nicht durch 2 teilbaren kategorisiert werden kann, lasst sie sich auch in die Mengen der primen bzw. der zusammengesetzten Zahlen unterteilen.

Eine zusammengesetzte Zahl ist das Pendant zur Primzahl, hat also mehr als zwei echte Teiler und kann als Produkt von mindestens zwei, von 1 verschiedenen Faktoren geschrieben werden, welche entweder prim oder wiederum zusammengesetzt sind.

3.1 Primfaktorzerlegung

Sei n eine derartige Zahl, so gilt n —a-b mit 1 <a, b< n . Angenommen a ist ebenfalls zusammengesetzt, so gilt a = k-m und ferner n —k-m-b . Unter jener Annahme konnen k,m und b fortlaufend in kleinere Faktoren zerlegt werden, bis schlieElich endlich viele, unzerlegbare Faktoren, d.h. nur Primzahlen in der Produktdarstellung von n auftreten.

Die Existenz sogenannter, fur jedes n eindeutiger, Primfaktorzerlegungen bildet die Kernaussage des Fundamentalsatzes der Arithmetik, die formal lautet:

Abbildung in dieser Leseprobe nicht enthalten

Jede Primzahl ist zugleich ihre Zerlegung selbst und auch negative ganze Zahlen konnen durch Voranstellen des Faktors —1 derart geschrieben werden.

3.2 ggT, kgV und mehr

Aus den Primfaktorzerlegungen zweier Zahlen lassen sich viele Eigenschaften direkt ablesen. Beispielsweise entspricht der groEte gemeinsame Teiler (ggT) von [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten] dem Produkt der groEten, in beiden Zahlen enthaltenen Primpotenzen 23-3-53=1272 .

Entgegen dazu bildet sich ihr kleinstes gemeinsames Vielfaches (kgV) [Abbildung in dieser Leseprobe nicht enthalten] aus dem Produkt aller, in ihrer hochsten Potenz vorkommenden Primfaktoren. Taucht keine Primzahl der einen Zerlegung in der der anderen auf, so sind die gewahlten Zahlen teilerfremd.

Des Weiteren ist die x -te Wurzel einer naturlichen Zahl n nur dann ganzzahlig, wenn x jeden Exponenten der Primfaktorzerlegung von n restlos teilt, da andernfalls das Produkt nur teilweise radiziert werden kann.

[Abbildung in dieser Leseprobe nicht enthalten] ist beispielsweise eine Quadratzahl, da beide Exponenten gerade sind. Formal lautet diese Regel:

Abbildung in dieser Leseprobe nicht enthalten

3.3 Warum 1 keine Primzahl ist

Zu sagen, 1 ist schlicht per definitionem keine Primzahl, stimmt zwar, aber doch sehr trivial und als einzige Begrundung wenig sinnvoll. Historisch waren beide Ansichten durchaus vertreten, wobei heutzutage ihre Definition als nicht prime Zahl ublich ist.

Ware 1 eine Primzahl, so stunde dies im Widerspruch zum Fundamentalsatz der Arithmetik. Denn lasst sich jede nicht prime Zahl als Produkt von Primfaktoren schreiben, waren alle Primzahlen wegen[Abbildung in dieser Leseprobe nicht enthalten] ... auchzusammengesetzt.

[...]


1 Primalitat: die Eigenschaft einer Zahl, prim zu sein

Details

Seiten
15
Jahr
2012
ISBN (eBook)
9783656333920
Dateigröße
521 KB
Sprache
Deutsch
Katalognummer
v198872
Note
1,6
Schlagworte
primzahlen überblick

Autor

Teilen

Zurück

Titel: Primzahlen - ein Überblick