def: eine primzahl ist eine natürliche zahl, die genau zwei verschiedene teiler besitzt. ( 1 und die zahl selber )
anmerkung: 1 ist demnach keine primzahl

 

satz von euklid: es gibt unendlich viele primzahlen

beweis: (indirekt)

angenommen, es gäbe endlich viele primzahlen: p1, p2, p3 , ... pn
dann wird das produkt aller primzahlen gebildet und 1 addiert.
diese neue zahl ist nun entweder selber eine (neue) primzahl oder sie enthält einen primfaktor, der noch nicht vorgekommen ist.
nachdem man diesen vorgang stets aufs neue durchführen kann, ist die annahme von endlich vielen primzahlen falsch
und die behauptung somit richtig.

q.e.d.


fundamentalsatz der zahlentheorie:
jede natürliche zahl lässt sich auf eindeutige weise in primfaktoren zerlegen.

 d.h.


zum ausprobieren: primfaktoren.ggb


eines der spannensten kapitel ist jenes, das sich mit der frage beschäftigt, ob man eine ...

formel für die anzahl der primzahlen

angeben kann.

gauss hatte dazu eine gute näherung entwickelt, nämlich p(n) ~  n/ log(n)

riemann ging mit seiner zetafunktion:


so vor, dass er für x die komplexen zahlen einsetzte und die nullstellen suchte.
seine vermutung war, dass alle nullstellen d.h. punkte mit meeresniveau, entlang einer linie liegen, deren realteil 1/2 ist.
die nullstellen kombiniert mit der sog. fourieranalyse würden die treppenkurve p(n) liefern. 

euler hat diese zeta-funktion als produkt von primzahltermen dargestellt:


 

beweis siehe: eulerprodukt-riemannzeta.pdf

näheres nachzulesen in: marcus du sautoy: die musik der primzahlen, auf den spuren des größten rätsels der mathematik.
siehe auch: TeXbasierte Seite


in restklassen mod primzahl ist jede lineare gleichung eindeutig lösbar

begründung:
die struktur (Zp,+p,*p) ist ein körper, d.h. speziell zur multiplikativen operation *p gibt es inverse elemente (eine art kehrwert).

a*x + b = 0 (mod p) => a*x = -b (mod p) => x = -b * a' (mod p)

z.B.: 5x + 3 = 0 (mod 17) => 5x = -3 = 14 (mod 17) => x = 14*7 = 13 (mod 17)  weil 7 das inverse element von 5 ( 5*7=35 = 1 (mod p)).


euler (1707-1783) stellte einen formelmässigen zusammenhang zwischen π und den primzahlen her:

siehe dazu euler-pi-primzahlen.pdf
man liest ab, dass offenbar zwei sorten von primzahlen dabei eine wichtige rolle spielen: 
1.sorte: p lässt bei division durch 4 den rest 1
2.sorte: p lässt bei division durch 4 den rest 3

von der ersten sorte weiß man, dass sich alle diese primzahlen auf genau eine einzige weise als summe zweier quadratzahlen darstellen lassen:
5 = 1² + 2²
13 = 3² + 2²
17 = 1² + 4²
29 = 5² + 2²
37 = 7² + 2²
41 = 5² + 4²
53 = 7² + 2²
61 = 5² + 6²
...
leider haben diese eigenschaft auch endlos viele gewöhnliche zahlen, die nicht prim sind, etwa 20 = 4² + 2² oder 85 = 9² + 2² = 7² + 6²
eleganter beweis von don zagier: beweiszagier.pdf

eine weitere eigenschaft von primzahlen taucht im pascalschen dreieck auf:

1
1   1
1   2   1 
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
1   6  15  20  15   6   1
1   7  21  35  35  21   7   1
1   8  28  56  70  56  28   8   1
1   9  36  84 126 126  84  36   9   1
1  10  45 120 210 252 210 120  45  10   1
1  11  55 165 330 462 462 330 165  55  11   1
1  12  66 220 495 792 924 792 495 220  66  12  1 

... in jeder zeile, die zu einer primzahl gehört, teilt diese jeden binomialkoeffizienten ≠ 1. diese tatsache ist auch umkehrbar. wann teilt ein primfaktor einen binomialkoeffizienten?
binomialkoeffizient-mod-p.ggb
primfaktoren-in-binomialkoeffizient.ggb


unter primzahlzwillingen versteht man zwei primzahlen mit der differenz 2, etwa 3 und 5. es ist nicht bekannt, ob es unendlich viele primzahlzwillinge gibt.
die summe der kehrwerte aller primzahlen ist divergent, während die summe der kehrwerte aller primzahlzwillinge konvergiert.

satz von clement: p und p+2 sind genau dann primzahlzwillinge, wenn 4((p-1)!+1)+p durch p(p+2) teilbar ist.

um alle primzahlzwillinge bis zu einer oberen grenze g=(6n+5)²-1 zu ermitteln, kann wie folgt vorgehen:
sei 1<=m<=n
man schreibe folgende zahlenlisten auf:
x1 = 2m(3m-1)   und   y1 = 2m(3m+1)
x2 = x1 + 2m       und   y2 = y1 + 4m+1
x3 = x2 + 4m-1    und   y3 = y2 + 2m
x4 = x3 + 2m       und   y4 = y3 + 4m+1
x5 = x4 + 4m-1   und   y5 = y4 + 2m 
... bis zu g/6-1
die in diesen zahlenfolgen nicht vorkommenden zahlen multipliziere man mit 6 und vermindere bzw. vermehre sie um 1.
dann hat man sämtliche primzahlzwillinge bis zur obergrenze g.
z.b.:
n=1, g=120, g/6-1=19, m=1, 2m(3m-1)=4, 2m=2, 4m-1=3, 2m(3m+1) = 8, 4m+1=5.
dann lauten die beiden zahlenfolgen:
x-reihe: 4,6,9,11,14,16,19 und
y-reihe: 8,13,15

z 6z 6z-1 6z+1
1 6 5 7
2 12 11 13
3 18 17 19
5 30 29 31
7 42 41 43
10 60 59 61
12 72 71 73
17 102 101 103
18 108 107 109

primzahldrillinge sind von der form (p / p+1 / p+6), etwa 5,7,11 oder (p / p+4 / p+6) etwa 67,71,73

außer 3,5,7 gibt es keine drei unmittelbar aufeinander folgende primzahlen mit abstand 2, da eine davon sicher durch 3 teilbar ist.

primzahlvierlinge sind von der form (p / p+2 / p+6 / p+8) etwa 11, 13, 17, 19
primzahlfünflinge sind z.b. 97, 101, 103, 107, 109 und ein
ein primzahlsechsling sieht so aus: (p / p+4 / p+6 / p+10 / p+12 / p+16) etwa 7, 11, 13, 17, 19, 23

ein primzahlpalindrom liest sich vorwärts und rückwärts gleich, z.b. 2, 3, 11, 353, 10301, ... ungeklärt ist, ob es unendlich viele primzahlpalindrome gibt.

interessant ist auch die frage nach primzahlen, die rückwärts gelesen auch wieder eine primzahl liefern, etwa 13 und 31, 17 und 71,
es gibt auch eine ganze folge von primzahlen, die man folgendermaßen generieren kann:
7
73
739
7393
73939
739391
7393913
73939133
???

3
31
331
3331
33331
333331
3333331
33333331
333333331 = 17*10607853 schade!

sophie-germain-primzahlen sind primzahlen p, bei denen 2p+1 auch ein primzahl ist, etwa 5 und 2*5+1 = 11, 7 ist keine sophie-germain-primzahl.

primzahlen p>3 sind nachbarn von vielfachen von 6: primzahlenmod6.ggb
primzahlen p>2 sind nachbarn von vierlfachen von 4: primzahlenmod4.ggb


primzahltests:

(1) Satz von Fermat: ist p eine primzahl , dann gilt für alle a

p-1 = 1 mod p
damit kann man testen, ob eine zahl z eine primzahl ist: man prüft, ob  2z-1-1 durch z teilbar ist.
leider gibt es auch zahlen, die keine primzahlen sind und trotzdem diesen test bestehen.
z.b.: z=341 d.h. wenn z eine primzahl ist, dann ist 2z-1-1 durch z teilbar aber nicht umgekehrt.

(2) Wilsonscher satz: ist p eine primzahl, dann ist (p-1)!+1 durch p teilbar und umgekehrt.
damit kann man sicher testen, ob z eine primzahl ist: man prüft, ob (z-1)!+1 durch z teilbar ist.
ist dies der fall, dann ist z tatsächlich eine primzahl.
nachteil: der term (z-1)!+1 wächst sehr rasch zu riesigen monstern heran und erschwert die teilbarkeitsprüfung.

(3) pascalsches dreieck: ist p eine primzahl, dann teilt sie jeden binomialkoeffizienten, der zu (a+b)p gehört und umgekehrt.


im bereich der komplexen zahlen gibt es sog. gausssche primzahlen. das sind komplexe zahlen a+bi mit ganzzahligen Werte a und b
und folgenden bedingungen:
(1) a² + b² ist prim oder
(2) |a|=0, b prim und b ≡ 3 (mod 4) oder
(3) |b|=0, a prim und a ≡ 3 (mod 4)

  gauss-primzahlen.ggb

eulersche φ()-Funktion:

def: φ(z) ist die anzahl aller teilerfremden (ggt=1) zahlen, die kleiner sind als z. 


 beweis:

(1) φ(p) = p-1, wenn p prim

(2) φ(ab) =φ(a)φ(b)  multiplikativ

(3) φ(pn)= pn - pn-1 = pn(1-1/p)
regel nummer (3) gilt, weil es zu pn genau pn-1 nicht-teilerfremde zahlen gibt, nämlich:

1p,2p,3p,...,pn-1p
mit hilfe dieser drei regeln kann man die formel für φ(z) ableiten, indem man z in primfaktoren zerlegt:


alle primzahlpotenzen ergeben wieder z.

q.e.d.


euler hat nun einen interessanten zusammenhang formuliert:

satz von euler: aφ(m) = 1 (m)  für alle 1<=a

 

einen sonderfall dieser aussage hat schon fermat heraus gefunden:

satz von fermat: ap-1 = 1 (p)  wenn p prim und 1<=a

 

auf der basis dieses satzes haben rivest, shamir und adleman das sog. RSA-verfahren entwickelt -

ein verfahren zur verschlüsselung von daten:

 

sei N ein in natürlicher zahlendarstellung vorcodierte nachricht, m = p*q ein öffentlicher schlüssel mit p,q prim.

der sender besitzt einen sendeschlüssel s, der zu (p-1)(q-1) teilerfremd sein muss.

verschlüsselung:  Ns mod m => C (codierte nachricht)

der empfänger hat nun einen passenden empfängerschlüssel e.

entschlüsselung: Ce mod m => N (nachricht)

damit dies funktioniert, muss e die lösung folgender (diophantischer) gleichung sein: s e = 1  mod (p-1)(q-1)

warum?

es soll gelten: (Ns)e = N  (m) , d.h. Nse = N (m) oder Nse-1=1 (m)

φ(m) = (p-1)(q-1), weil m = p*q

lt.euler (fermat) gilt: Nφ(m) = 1 (m) ,d.h.  se - 1 = k (p-1)(q-1)  oder se =1  mod (p-1)(q-1)

Merken

Merken