Einträge mit dem Tag ‘Primzahlen’

Zum Tagesabschluß habe ich noch etwas heiteres, nämlich eine Suchanfrage: warum muss man bei primzahlen die vielfachen fon 11 nicht streichen?, will ein unbekannter Besucher wissen.

Da kann ich nur sagen: die Frage ist falsch gestellt. Wenn man mit dem Sieb des Eratosthenes Primzahlen bestimmen will, sind die Vielfacher von elf durchaus zu streichen -- genauso wie die aller anderen Primzahlen. Sind allerdings nur die Primzahlen bis N=100 gefragt, kann man nach der sieben aufhören: es genügt immer, bis zur Wurzel von N (hier also 10) zu prüfen.

Das sieht man so: angenommen, es gibt einen Teiler von nN (nennen wir ihn a), mit a>√N. Dann ist aber auch b = n/aN/a < N/√N = √N, also b<√N, Teiler von n; und so erkennen wir auch dann, daß n nicht prim ist, wenn wir nur bis √N prüfen.

Gute Nacht.

Comments Off on Gesiebt

Referrer sind doch eine tolle Sache — so bekommt man erst mit, was die Be-sucher denn so alles suchen. Einer wollte neulich alle primzahlen aufgezählt haben.
Damit kann ich leider nicht dienen, denn es gibt eine ganze Menge Primzahlen — unendlich viele, um genau zu sein.

Viel

Geht es noch genauer? Unendlich ist ja nicht gleich unendlich. Nimmt man zum Beispiel nur die geraden Zahlen (2, 4, 6, 8, 10, …), so gibt es davon offenbar[1] weniger als von den natürlichen Zahlen (1, 2, 3, 4, …). Von den "runden" Zahlen (1, 10, 100, 1000, …) gibt es dann noch weniger. Wie mag es wohl mit den Primzahlen aussehen?
Es gibt so viele Primzahlen, daß Primreihe

Häh?

OK, der Reihe nach; zuerst stellt sich die Frage, was da eigentlich steht. Das ist relativ einfach. Wenn wir alle Primzahlen nehmen (pϵP), zu jeder den Kehrwert bilden (1/p), und diese Kehrwerte dann aufsummieren (Ʃ), dann wird das Ergebnis unendlich groß. Auf den ersten Blick ist das vielleicht nicht verwunderlich; immerhin addieren wir unendlich viele Zahlen, die alle positiv sind.
Wenn wir aber statt 1/p die reziproken Zweierpotenzen addieren, dann ist das Ergebnis durchaus endlich: 1/2+1/4+1/8+…=1. Warum? Naja, 1/2 ist die Hälfte von 1; 1/4 ist die Hälfte von dem, was dann noch zu 1 fehlt, und so weiter:
konvergent

Wenn die Zahlen, deren Kehrwerte ich addiere, also schnell genug größer werden, dann kann die Reihe[3] konvergieren, also eine endliche Zahl als Ergebnis haben. Daß die Reihe der reziproken Primzahlen divergiert, bedeutet also, daß sie nicht sehr schnell größer werden — daß es also recht viele von ihnen gibt.

Langsam

Was heißt nicht sehr schnell? Nun, die Reihe der reziproken natürlichen Zahlen, 1+1/2+1/3+1/4+…, divergiert, i.e. die natürlichen Zahlen wachsen in diesem Sinne langsam. Die Quadratzahlen wachsen dagegen schnell, 1+1/4+1/9+1/16+… konvergiert nämlich[4] — nimmt man stattdessen dritte oder vierte Potenzen, so wachsen die Zahlen natürlich schneller, und die Reihen konvergieren auch. Man kann zeigen, daß Ʃ1/nr immer konvergiert, solange r nur größer als 1 ist. Es reicht, r=1,001 (oder noch kleiner) zu wählen. Das heißt, daß die Folge der Primzahlen tatsächlich sehr langsam wachsen muß, damit die Reihe divergiert.

An's Eingemachte

Behaupten kann man viel, wenn der Tag lang ist. Mathematiker wollen aber immer Beweise dafür sehen. Der, den ich hier vorführen möchte, stammt von dem berühmten Ungarn Erdős. Ich folge dabei dem Buch von Aigner und Ziegler[5].

Der Beweis ist wieder ein Widerspruchsbeweis, i.e. wir nehmen an, daß die Behauptung gerade nicht stimmt, rechnen ein bißchen herum und finden dabei einen Widerspruch. Daraus folgt dann, daß die Annahme falsch war.

Nehmen wir also an, daß die Reihe konvergiert. Wenn wir nun die ersten Summanden überspringen, dann wird die Gesamtsumme kleiner, und wenn wir genügend Summanden überspringen, können wir die Gesamtsumme kleiner als 1/2 machen.[6]

Wählen wir also k genügend groß, und denken wir uns noch irgendeine Zahl N aus, mit der wir die ganze Ungleichung multiplizieren, dann gilt:
übersprungen

Wenn wir jetzt alle Zahlen betrachten, die nicht größer sind als N, dann gibt es solche, die sich durch eine Primzahl teilen lassen, die in unserer verkürzten Reihe vorhanden ist; ihre Anzahl wollen wir b nennen. Und es gibt solche, die nur Primteiler besitzen, die unter den ersten k Primzahlen sind und deswegen nicht in der verkürzten Reihe vorkommen; ihre Anzahl sei s. Weil alle Zahlen entweder zu der einen oder anderen Kategorie gehören müssen, ist s+b=N.

Wie groß ist b? Nun, für eine Primzahl pi gibt es Teiler zählen Zahlen, die durch sie teilbar sind. Wenn wir diesen Ausdruck über alle Primzahlen summieren, dann liegen wir vielleicht zu hoch, aber sicher nicht zu niedrig[7].
Wenn wir also summieren, dann steht wieder unsere Ungleichung von oben da, und es gilt: b < N/2.

Wie sieht es für s aus? Das geht anders, und zwar so: Wir schreiben jede Zahl n, die zu s zählt, als n=a·q2. Dabei ist a das Produkt aller Primfaktoren, die in n nur einmal vorkommen. Zum Beispiel ist 150=2·3·5·5, also a=2·3=6 und q=5.
Um die Frage zu klären, wie groß s ist, müssen wir also überlegen, wie viele verschiedene a und q es gibt. Das ist einfach: in a kommt jede Primzahl einmal oder keinmal vor, das sind zwei Möglichkeiten pro Primzahl. Da für s nur die ersten k Primzahlen in Frage kommen, sind das 2·2·2…=2k Möglichkeiten. Bei q machen wir es uns ganz einfach: q2n, und nN, also q ≤ √N.

Damit ist s ≤ 2kN.

Widerworte

Am Anfang hatten wir uns ja ein N ausgedacht, aber alle Überlegungen waren völlig allgemein. Wir können uns jetzt also noch umentscheiden und zum Beispiel N=22k+2 nehmen. Dann ist s ≤ s2k+1 (Einsetzen in die letzte Gleichung vom vorigen Absatz), also kleiner als N/2.

Weil b aber auch kleiner als N/2 ist, muß s+b kleiner als N sein.
Am Anfang hatten wir aber gesehen, daß s+b gerade gleich N ist. Beides gleichzeitig geht nicht, und da haben wir unseren Widerspruch.

Ende

Also, lieber unbekannter Google-User: es gibt nicht nur unendlich viele, sondern sogar verdammt viele Primzahlen, und die kann ich Dir unmöglich alle aufzählen.

Noten

[1] Ganz so einfach ist die Sache eigentlich nicht, dann auf eine sehr intuitive[2] Art gibt es gleich viele gerade und natürliche Zahlen. Das hört sich jetzt seltsam an, weil ja jede gerade Zahl eine natürliche ist, es aber auch natürliche Zahlen gibt, die nicht gerade sind — die ungeraden eben. Man kann aber von unendlichen Mengen durchaus einige Elemente wegnehmen, ohne daß die Menge kleiner würde.
In der Tat läßt sich diese Eigenschaft als Definition von unendlich verwenden.

[2] Vielleicht schreibe ich dazu noch einen Eintrag.

[3] Eine Reihe ist, vereinfacht gesagt, eine Summe unendlich vieler Zahlen.

[4] Und zwar gegen π2/6.

[5] Dieses Buch, das in Anlehnung an eine Idee von Erdős Das BUCH der Beweise heißt, kann man gar nicht genug loben. Deswegen wandert es jetzt erstmal in meine Sidebar.

[6] Das ist eine Eigenschaft von Grenzwerten. Letztlich ist der Grund der, daß die Reihe sich an ihr Ergebnis heranschleicht.

[7] Zu hoch deshalb, weil wir einiges doppelt zählen: 6 ist zum Beispiel durch 2 und 3 teilbar, und wir würden sie einmal bei den Vielfachen von 2, einmal bei denen von 3 zählen.

Comments Off on Wie viele?

Heute möchte ich mich mit einem Thema beschäftigen, das bei den meisten Menschen kein gutes Ansehen genießt: Mathematik. (Halt! Nicht wegklicken!)
Dabei soll es nicht um lustige Zahlenspielereien oder nützliche Rechenregeln gehen; vielmehr geht es mir um die Schönheit, die mathematische Aussagen und Beweise an den Tag legen, wenn man sie nicht als Mittel, sondern als Zweck betrachtet.
Die Idee dabei ist, einzelne Themen herauszugreifen und (hoffentlich) auch für Mathematik-Abstinenzler verständlich darzustellen.

Zu Anfang soll es um Primzahlen gehen. Die haben viele Vorteile: die meisten Menschen wissen, was Primzahlen sind; sie haben keine direkte Anwendung außerhalb der Mathematik (so daß man nicht so leicht abgelenkt wird); und man kann viele lustige Dinge mit ihnen anstellen.

Wenn der Mathematiker einen neuen Begriff einführt, dann tut er das mit einer Definition, die genau sagt, wie der Begriff zu verstehen ist. Primzahlen sind bekanntlich Zahlen, die nur durch Eins und sich selbst teilbar sind. Etwas genauer kann man definieren:
Eine natürliche Zahl n, deren Teilermenge genau zwei Elemente enthält, heißt Primzahl.
Daraus folgt, daß die Eins keine Primzahl ist, denn ihre Teilermenge enthält nur ein Element. Die umgangssprachliche Formulierung nur durch Eins und sich selbst teilbar ist da etwas unklar, was später zu Verwirrung führen könnte.

Welche konkreten Zahlen sind denn nun prim? Die ersten sind schnell aufgezählt: 2, 3, 5, 7, 11, 13, ...
Und wie geht es weiter? Vor allem: ist irgendwann Schluß, oder gibt es unendlich viele Primzahlen? Einerseits ist nicht recht einzusehen, warum es unendlich viele natürliche Zahlen, aber nur endlich viele Primzahlen geben soll; andererseits ist unsere Unfähigkeit, uns eine Welt mit endlich vielen Primzahlen vorzustellen, ein ziemlich schwaches Argument. Es muß also ein Beweis her. Vorher formulieren wir noch schnell einen Satz, der die zu beweisende Aussage formuliert:
Es gibt unendlich viele Primzahlen.
Eine häufig verwandte Methode ist die des Beweises durch Widerspruch: man nimmt einfach das Gegenteil der Behauptung an und leitet daraus einen Widerspruch her. Wenn die Schlußfolgerungen alle einwandfrei sein, muß die ursprüngliche Annahme falsch sein — und damit die Behauptung wahr.
Wir nehmen also an, es gäbe nur endlich viele Primzahlen, sagen wir n Stück. Diese numerieren wir durch: p1, p2, ..., pn. Betrachten wir nun die Zahl x, die um eins größer als das Produkt aller Primzahlen ist: x=p1p2...pn+1. Jede Zahl besitzt einen Primteiler, also auch x — das ist aber ein Widerspruch, denn p1p2...pn ist ja per Konstruktion durch alle Primzahlen teilbar; zwei aufeinanderfolgende Zahlen haben aber keine gemeinsamen Teiler (außer 1).
[Das sieht man so: wenn n und n+1 beide durch p teilbar sind, dann gibt es x und y, so daß n=xp und n+1=yp, also xp+1=yp. Damit ist aber (y–x)p=1, also auch Eins durch p teilbar => Widerspruch, denn Eins besitzt (außer sich selbst) keine Teiler.]

Die Annahme, es gebe nur endlich viele Primzahlen, führt also auf einen Widerspruch, so daß es unendlich viele Primzahlen geben muß, q.e.d.

Comments Off on Prima Zahlen