1.Thema ab Klasse 11: Elementare Zahlentheorie I (Teilbarkeit und Primzahlen) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:19 Sa 14.02.2004 | | Autor: | Stefan |
Fangen wir mal mit meinem Lieblingsthema der Mathematik an, nämlich der Elementaren Zahlentheorie.
Es gibt einige Grundbegriffe und Aussagen, die ihr kennen solltet. Wir verzichten hier auf Beweise. Die Beweise sind trivial und die Aussagen auch anschaulich klar. Es ist eigentlich schon wichtig, dass man die Beweise sauber hinbekommt, aber das ist nicht das Ziel dieses Forums (sondern wäre vielleicht das Ziel einer Vorlesung zur Elementaren Zahlentheorie). Man braucht die Aussagen aber, um die Wettbewerbsaufgaben effektiv lösen zu können, sie geben einem einen Fundus an Werkzeugen, aus dem man schöpfen kann.
Begriff der Teilbarkeit in [mm]\red{\IZ}[/mm]
Es seien [mm]\red{a,b \in \IZ}[/mm]. Man sagt, [mm]\red{a}[/mm] teilt [mm]\red{b}[/mm] (und schreibt dafür [mm]\red{a\vert b}[/mm]), wenn es ein [mm]\red{q \in \IZ}[/mm] gibt mit [mm]\red{b=aq}[/mm]. Dann sagt man auch: [mm]\red{b}[/mm] ist durch [mm]\red{a}[/mm] teilbar.
Beispiel: Es gilt: [mm](-3)\vert 24[/mm] wegen [mm]24=(-3)\cdot(-8)[/mm].
Eine wichtige Aussagen über Teilbarkeit in [mm]\IZ[/mm]:
Satz:
1. Für alle [mm]\blue{a,b,c \in \IZ}[/mm] gilt:
[mm]\blue{a \vert b}[/mm], [mm]\blue{b \vert c}[/mm] [mm]\blue{\Rightarrow}[/mm] [mm]\blue{a \vert c}[/mm].
Mit anderen Worten: Teiler von Teilern einer vorgegebenen ganzen Zahl sind selber Teiler dieser Zahl.
2. Für alle [mm]\blue{a,b,d \in \IZ}[/mm] gilt:
[mm]\blue{d \vert a}[/mm], [mm]\blue{d \vert b}[/mm] [mm]\blue{\Rightarrow}[/mm] [mm]\blue{d \vert(ax+by)}[/mm] für alle [mm]\blue{x,y \in \IZ}[/mm]
Mit anderen Worten: Teilt eine ganze Zahl zwei andere ganze Zahlen, so auch jede ganzzahlige Linearkombination dieser Zahlen.
Insbesondere folgen aus [mm]\blue{d \vert a}[/mm] und [mm]\blue{d \vert b}[/mm] die Beziehungen [mm]\blue{d \vert (a+b)}[/mm] und [mm]\blue{d \vert (a-b)}[/mm].
3. Wenn zwei der Terme der Gleichung [mm]\blue{a+b=c}[/mm] mit [mm]\blue{a,b,c \in \IZ}[/mm] durch [mm]\blue{d \in \IZ}[/mm] teilbar sind, dann auch der dritte.
Wichtig ist, dass in [mm]\IZ[/mm] eine Division mit Rest möglich ist:
Satz:
Für alle [mm]\blue{a \in \IZ}[/mm] und alle [mm]\blue{b \in \IN}[/mm] gibt es genau ein [mm]\blue{q \in \IZ}[/mm] und genau ein [mm]\blue{r \in \IZ}[/mm] mit
[mm]\blue{a=bq + r \quad \mbox{und} \quad 0 \le r < b}[/mm].
Beispiel:
Für [mm]a=-10[/mm] und [mm]b=3[/mm] gilt:
[mm]-10 = 3\cdot(-4) + 2[/mm],
also:
[mm]-10 = 3q + r[/mm] mit [mm]q=-4[/mm] und [mm]0 \le r=2<3[/mm].
Man nennt [mm]q[/mm] den Quotienten und [mm]r[/mm] den Rest bei der Division von [mm]a[/mm] durch [mm]b[/mm].
Es seien [mm]a, b \in \IZ[/mm], [mm]a,b \ge 0[/mm] (also nichtnegative ganze Zahlen) und es gelte: [mm]a+b > 0[/mm] (d.h. mindestens eine der beiden Zahlen sei größer als [mm]0[/mm]).
Dann bezeichnen wir mit [mm]\red{ggT(a,b)}[/mm] den größten gemeinsamen Teiler von [mm]a[/mm] und [mm]b[/mm] und mit [mm]\red{kgV(a,b)}[/mm] das kleinste gemeinsame Vielfache von [mm]a[/mm] und [mm]b[/mm].
Es gilt etwa für alle [mm]a \in \IN[/mm]:
[mm]ggT(a,1)=1[/mm] ,
[mm]ggT(a,a) = a[/mm] ,
[mm]ggT(a,0) = a[/mm] (jede ganze Zahl [mm]a[/mm] teilt [mm]0[/mm] !),
und für alle [mm]a,b \in \IZ, a,b \ge 0, a+b > 0[/mm]:
[mm]ggT(a,b) = ggT(b,a)[/mm] .
Wir nennen [mm]a[/mm] und [mm]b[/mm] relativ prim, wenn
[mm]ggT(a,b)=1[/mm]
gilt. Für [mm]0\le b \le a[/mm] gilt:
[mm]ggT(a,b) = ggT(b,a-b)[/mm].
D.h. man kann [mm]ggT(a,b)[/mm] sukzessive ausrechnen, indem man wiederholt von der größeren der beiden Zahlen die kleinere abzieht und dann jeweils den größten gemeinsamen Teiler von der kleineren der beiden Zahlen und der Differenz der beiden Zahlen bildet.
Beispiel:
[mm]ggT(48,30) = ggT(30,18) = ggT(18,12) = ggT(12,6) = ggT(6,6) = 6[/mm].
Insbesondere gilt:
Haben wir eine Division mit Rest durchgeführt:
[mm]a = bq+r[/mm],
so gilt:
[mm]ggT(a,b) = ggT(b,a-b) = ggT(b,a-2b) = \ldots = ggT(b,a-qb) = ggT(b,r)[/mm].
(An dieser Stelle sei auf den Euklidischen Algorithmus hingewiesen, den ihr hier nachlesen könnt:
![[]](/images/popup.gif) http://www.math.uni-leipzig.de/~gittel/LinAlg/EuklAlg.pdf )
Satz:
Der [mm]\blue{ggT(a,b)}[/mm] kann als Linearkombination von [mm]\blue{a}[/mm] und [mm]\blue{b}[/mm] mit ganzzahligen Koeffizienten dargestellt werden, d.h. es gibt [mm]\blue{x , y \in \IZ}[/mm] mit
[mm]\blue{ggT(a,b) = ax + by}[/mm].
Insbesondere gilt: Wenn [mm]\blue{a}[/mm] und [mm]\blue{b}[/mm] relativ prim sind, dann hat die Gleichung
[mm]\blue{1 = ax + by}[/mm]
eine ganzzahlige Lösung [mm]\blue{(x,y)}[/mm].
Die Zahlen [mm]x[/mm] und [mm]y[/mm] bekommt man zum Beispiel aus dem Euklidischen Algorithmus.
Beispielaufgabe:
Bestimme [mm]ggT(84,315)[/mm] und stelle [mm]ggT(84,315)[/mm] als ganzzahlige Linearkombination von [mm]84[/mm] und [mm]315[/mm] dar!
Lösung:
Mit dem Euklidischen Algorithmus berechnen wir (fortlaufende Division mit Rest):
[mm]315= 84\cdot 3 +63[/mm]
[mm]84 = 63\cdot 1 + 21[/mm]
[mm]63 = 21\cdot 3 + 0[/mm].
(Wenn hinten eine [mm]0[/mm] steht, dann ist der Euklidische Algorithmus beendet. Die Zahl, wo jetzt die [mm]21[/mm] steht, ist dann der größte gemeinsame Teiler der beiden Ausgangszahlen.)
Genauer:
[mm]ggT(315,84) = ggT(84,63) = ggT(63,21) = 21[/mm].
Durch "Immer-wieder-ineinander-einsetzen", beginnend mit der vorletzten der obigen Gleichungen aus dem Euklidischen Algorithmus, bekommt man jetzt die gewünschte Darstellung:
[mm]21 = 84 - 63\cdot 1 = 84 - (315 - 84 \cdot 3)= -1 \cdot 315 + 4 \cdot 83[/mm].
Es gilt also:
[mm]ggT(315,84) = 21 = x\cdot 315 + y \cdot 83[/mm]
mit [mm]x=-1[/mm] und [mm]y=4[/mm].
(Ende des Beispiels.)
Es gilt die wichtige Aussage:
[mm]\blue{ggT(a,b) \cdot kgV(a,b) = a\cdot b}[/mm],
Hat man also etwa [mm]ggT(a,b)[/mm] (zum Beispiel mit dem Euklidischen Algorithmus) bestimmt, so erhält man [mm]kgV(a,b)[/mm] durch
[mm]kgV(a,b) = \frac{a\cdot b}{ggT(a,b)}[/mm].
Primzahlen
Man nennt eine positive ganze Zahl (also ein natürliche Zahl) eine Primzahl, wenn sie genau zwei Teiler hat.
Satz
Ist [mm]\blue{p}[/mm] eine Primzahl und sind [mm]\blue{a}[/mm] und [mm]\blue{b}[/mm] ganze Zahlen, so gilt:
[mm]\blue{p \vert(ab) \quad \Rightarrow \quad [\ p\vert a \quad \mbox{oder} \quad p \vert b\ ]}[/mm].
Mit anderen Worten: Teilt eine Primzahl ein Produkt zweier ganzer Zahlen, so teilt sie mindestens einer der beiden Faktoren.
Satz
Jede natürliche Zahl lässt sich (bis auf die Reihenfolde) in eindeutiger Weise als Produkt von Primzahlen schreiben.
Man spricht dann von der Primfaktorzerlegung dieser Zahl.
Beispiel:
[mm]630 = 2\cdot 3^2 \cdot 5 \cdot 7[/mm].
Satz (Euklid)
Es gibt unendlich viele Primzahlen.
(Wer den Beweis dazu sehen will, der melde sich bitte hier im Forum.)
Es gibt beliebig große Lücken zwischen den Primzahlen, denn für alle [mm]n \in \IN[/mm] sind die Zahlen
[mm]n! + 2,\, n! + 3, \, \ldots, \, n! + n[/mm]
alle nicht prim. (Warum nicht? Nun: [mm]n! + 2 = (1\cdot 2 \cdot 3 \cdots n) + 2[/mm] ist durch [mm]2[/mm] teilbar, [mm]n! + 3 = (1\cdot 2 \cdot 3 \cdots n) + 3[/mm] ist durch [mm]3[/mm] teilbar, usw.)
Ist [mm]n[/mm] nicht prim (also keine Primzahl), dann gilt für den kleinsten Primteiler [mm]p[/mm] (ein Primteiler ist ein Teiler, der zugleich eine Primzahl ist) die Beziehung:
[mm] p \le \sqrt{n}[/mm].
Satz
Jede Primzahl [mm]\blue{p>3}[/mm] ist von der Form
[mm]\blue{p = 6n \pm 1}[/mm].
Beispiele:
[mm]5 = 6\cdot 1 - 1[/mm], [mm]7 = 6 \cdot 1 + 1[/mm], [mm]11= 6 \cdot 2 - 1[/mm], [mm]13 = 6 \cdot 2 + 1[/mm], [mm]17 = 6 \cdot 3 - 1[/mm], [mm]\ldots[/mm]
Achtung! Umgekehrt ist aber natürlich nicht jede Zahl von der Form [mm]\red{6n \pm 1}[/mm] eine Primzahl. So ist zum Beispiel:
[mm]\red{6 \cdot 4 + 1 = 25}[/mm]
keine Primzahl.
Wer Fragen zu dem Text hat oder zu gewissen Aussagen oder Sätzen einen Beweis sehen will, der melde sich bitte im Forum (einfach eine Frage zu diesem Beitrag stellen).
Die ersten Aufgaben zu diesem Thema folgen heute abend oder morgen.
Liebe Grüße
Stefan
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Sa 21.02.2004 | | Autor: | Stefan |
Hallo zusammen!
Wie versprochen, jetzt noch ein paar Beispielaufgaben, historische Anmerkungen, Tipps und Tricks zum Thema:
Wenn man zeigen will, dass eine gewisse ganze Zahl einen algebraischen Ausdruck mit Werten in der Menge der ganzen Zahlen teilt, dann sind es im Wesentlichen immer die gleichen Tricks, die man anwendet.
Die wichtigste Beziehung ist diejenige:
[mm]\blue{(a-b) \vert (a^n-b^n)}[/mm] für alle [mm]\blue{n \in \IN}[/mm].
Genauer gilt:
[mm](a-b) \cdot \sum\limits_{i=0}^{n-1} a^i b^{n-1-i} = a^n - b^n[/mm].
Daraus folgt wegen
[mm]a^n + b^n = a^n - (-b)^n[/mm] für alle ungeraden [mm]n \in \IN[/mm] und [mm]a-(-b) = a+b[/mm]
die ebenfalls wichtige Aussage:
[mm]\blue{(a+b) \vert (a^n+b^n)}[/mm] für alle ungeraden [mm]\blue{n \in \IN}[/mm].
Für gerades [mm]n \in \IN[/mm] hat man leider im Allgemeinen nicht so schöne Beziehungen. So kann man etwa den Ausdruck
[mm]x^2 + y^2[/mm]
nur dann faktorisieren, wenn [mm]2xy[/mm] ein Quadrat ist. (Wie das dann geht, ist klar: Man addiert und subtrahiert [mm]2xy[/mm] und wendet erst die 1., dann die 3. Binomische Formel an.)
Ein wichtiger Spezialfall für ein gerades [mm]n \in \IN[/mm] ist die berühmte Identität von Sophie Germain:
[mm]\blue{a^4 + 4b^4 = a^4 +4a^2b^2 + 4b^4 - 4a^2 b^2}[/mm]
[mm]\blue{= (a^2 + 2b^2)^2 - (2ab)^2}[/mm]
[mm]\blue{= (a^2 + 2b^2 +2ab)(a^2+2b^2-2ab)}[/mm].
Sobald ([mm]|a-b|>0[/mm] und [mm]b>0[/mm]) oder [mm]b>1[/mm] gilt, gilt für den kleineren der beiden Faktoren:
[mm]a^2 + 2b^2 - 2ab = (a-b)² + b² >1[/mm],
und man hat eine echte Faktorisierung, d.h. es handelt sich bei [mm]a^4 + 4b^4[/mm] um keine Primzahl.
Viele (schwierige) Mathe-Olympiade-Aufgabe beruhen auf dieser Identität von Sophie Germain. Zum Beispiel wurde 1978 das folgende Problem gestellt, das nur von sehr wenigen Schülerinnen und Schülern gelöst wurde:
Aufgabe 1:
Zeige: [mm]\green{n > 1 \ \Rightarrow \ n^4 + 4^n}[/mm] ist niemals prim.
Lösung:
Wenn [mm]n[/mm] gerade ist, dann ist auch [mm]n^4 + 4^n[/mm] gerade und größer als [mm]2[/mm], also nicht prim.
Es genügt also die Behauptung für ungerades [mm]n[/mm] zu zeigen und wir können daher
[mm]n = 2k+1[/mm] mit einem [mm]k \in \IN[/mm]
annehmen. Jetzt versuchen wir auf die Struktur [mm]a^4 + 4b^4[/mm] aus der Identität von Sophie Germain zu kommen. Sobald uns das gelungen ist, sind wir fertig, denn dann können wir ja den Term nach dieser Identität faktorisieren und haben gezeigt (falls beide Faktoren größer als [mm]1[/mm] sind), dass der Term nicht prim ist.
Nun, es gilt:
[mm]n^4 + 4^n = (2k+1)^4 + 4^{2k+1} = (2k+1)^4 + 4 \cdot 4^{2k} = (2k+1)^4 + 4 \cdot 2^{4k} = (2k+1)^4 + 4 \cdot (2^k)^4[/mm]
und wir haben die Identität von Sophie Germain mit [mm]a=2k+1[/mm] und [mm]b=2^k[/mm].
Wegen [mm]b=2^k>1[/mm] für alle [mm]k>0[/mm] (was nach Voraussetzung wegen [mm]n>1[/mm] gilt!) folgt die Behauptung.
Dieses Problem tauchte zum ersten Mal im Mathematics Magazine im Jahr 1950 auf. Für die Internationale Mathematik-Olympiade 1978 wurde es von A. Makowski aus dem polnischen Team vorgeschlagen.
In der nationalen russischen Mathe-Olympiade tauchte einst das folgende Problem auf (es war eine Aufgabe für die 8. Klasse):
Aufgabe 2:
Ist [mm]\green{4^{545} + 545^4}[/mm] prim ?
Lösung:
Nur wenige Schülerinnen und Schüler sahen die Lösung, obwohl auch andere Aufgaben auf der Identität von Sophie Germain basierten und sie daher diesen wichtigen Trick kannten. Erstaunlich! Denn so schwierig ist es ja nicht zu sehen, dass
[mm]4^{545} + 545^4 = 545^4 + 4 \cdot 4^{544} = 545^4 + 4\cdot (4^{136})^4[/mm]
gilt und damit wiederum die Identität von Sophie Germain (diesmal mit [mm]a=545[/mm] und [mm]b=4^{136}>1[/mm]) angewendet werden kann.
Die nächsten Beispielaufgaben folgen bald. Das ist hier wirklich hohes Niveau, nämlich das Niveau der (inter-)nationalen Mathe-Olympiade für die Mittelstufe in den fortgeschrittenen Runden, also bitte nicht frustriert sein, wenn euch das schwierig vorkommt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:49 Di 24.02.2004 | | Autor: | Stefan |
Ich möchte euch noch mal zwei weitere Aufgaben mit Lösungen vorstellen. Die zweite Aufgabe finde ich persönlich echt hart, die erste dagegen ist Routinearbeit. Es handelt sich wieder um Original-Wettbewerbsaufgaben aus der Vergangenheit.
Aufgabe 1:
Zeige, dass der Ausdruck [mm]\red{2^{2^n}} + 2^{2^{n-1}} + 1}[/mm] für alle [mm]\red{n \in \IN}[/mm] mindestens [mm]\red{n}[/mm] verschiedene Primteiler hat.
Lösung:
Die Lösung ist nur verständlich für Mitglieder, die das Prinzip der vollständigen Induktion kennen (auf das wir noch ausführlich zu sprechen kommen werden, aber noch nicht an dieser Stelle). Alle anderen bitte zur nächsten Aufgabe weiterspringen... 
Klar: Eine Behauptung, die für alle [mm]n \in \IN[/mm] gelten soll, versuchen wir natürlich durch vollständige Induktion zu beweisen.
Der Induktionsanfang ist hierbei trivial, da jede Zahl mindestens einen Primteiler besitzt.
Wir nehmen nun an, wir hätten für [mm]n[/mm] bereits gezeigt, dass [mm]2^{2^n}} + 2^{2^{n-1}} + 1[/mm] mindestens [mm]n[/mm] verschiedene Primteiler besitzt und wollen dies nun für [mm]n+1[/mm] beweisen.
Dann ist also zu zeigen:
[mm]\blue{2^{2^{n+1}}} + 2^{2^{n}} + 1}[/mm] besitzt mindestens [mm]\blue{n+1}[/mm] verschiedene Primteiler.
Es ist vollkommen klar, wie wir vorgehen. Oder? Wir versuchen natürlich diesen Ausdruck zu faktorisieren und hoffen, dass einer der beiden Faktoren gleich [mm]2^{2^{n}}} + 2^{2^{n-1}} + 1[/mm] ist, auf den wir dann die Induktionsvoraussetzung anwenden können.
Nun gilt aber allgemein die wichtige Identität (unbedingt nachvollziehen und sich den Trick merken!):
[mm]\green{x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2+1)^2 - x^2 = (x^2 - x + 1)(x^2 + x + 1)}[/mm].
Speziell für [mm]x=2^{2^{n-1}}[/mm] gilt:
[mm]x^2 = 2^{2^{n-1}\cdot 2} = 2^{2^n}[/mm]
und
[mm]x^4 = 2^{2^{n-1}\cdot 4}= 2^{2^{n+1}}[/mm],
also:
[mm]2^{2^{n+1}}} + 2^{2^{n}} + 1 = (2^{2^n} - 2^{2^{n-1}} + 1) (2^{2^n} + 2^{2^{n-1}} + 1)[/mm].
Nach Induktionsvoraussetzung besitzt der zweite der beiden Faktoren mindestens [mm]n[/mm] Primteiler. Wenn wir nun zeigen können, dass beide Faktoren teilerfremd sind, dann sind wir fertig, denn dann besitzt der erste Faktor mindestens einen weiteren Primteiler, der sich von den [mm]n[/mm] Primteilern des zweiten Faktors unterscheidet, d.h. [mm]2^{2^{n+1}}} + 2^{2^{n}} + 1[/mm] besitzt dann [mm]n+1[/mm] verschiedene Primteiler.
Aber: Jeder gemeinsame Teiler der beiden Faktoren müsste auch deren Differenz teilen, also den Term [mm]2 \cdot 2^{2^{n-1}} = 2^{2^{n-1}+1}[/mm]. Da [mm]2[/mm] der einzige Primteiler dieser Differenz ist, aber [mm]2[/mm] die beiden Faktoren selbst nicht teilt, folgt die Behauptung.
Die nächste Aufgabe geht ähnlich, ich persönlich finde sie aber recht hart.
(Für die Teilnehmer der Internationalen Mathe-Olympiade dagegen ist so etwas eine lockere Aufwärmübung. )
Aufgabe 2:
Finde alle Primzahlen der Form [mm]\red{n^n+1}[/mm], die kleiner als [mm]\red{10^{19}}[/mm] sind.
Lösung:
Für [mm]n=1[/mm] und [mm]n=2[/mm] bekommen wir die beiden Primzahlen [mm]2[/mm] und [mm]5[/mm].
Offenbar kann [mm]n>1[/mm] nicht ungerade sein, denn dann wäre [mm]n^n+1>2[/mm] gerade, also keine Primzahl.
Somit muss in der Primfaktorzerlegung von [mm]n[/mm] mindestens eine [mm]2[/mm] vorkommen.
Wir haben also zunächst eine Darstellung:
[mm]n = 2^s \cdot p_2^{s_2} \cdots p_m^{s_m}[/mm]
mit [mm]s\ge1[/mm], [mm]p_2, \ldots p_m[/mm] paarweise verschiedene und von [mm]2[/mm] verschiedene Primzahlen und [mm]s_2,\ldots,s_m \in \IN[/mm].
Bis dahin war es ja einfach. Aber jetzt kommt das Hauptargument.
Wir wissen allgemein, dass
[mm](a+b)|(a^j+b^j)[/mm]
für ungerades [mm]j[/mm] gilt. Wenden wir diesen Satz nun auf
[mm]a = n^{2^s}[/mm], [mm]b=1[/mm] und [mm]j=p_2^{s_2} \cdots p_m^{s_m}[/mm] an, so folgt:
[mm](n^{2^s} + 1) | (n^n + 1)[/mm],
d.h. [mm]n^n+1[/mm] wäre dann keine Primzahl. Auszulösen ist dieser Widerspruch nur dann, wenn [mm]n[/mm] keine anderen Primteiler als [mm]2[/mm] enthält, d.h. wenn [mm]n=2^s[/mm] gilt.
In diesem Fall kann man [mm]s[/mm] allgemein wie folgt schreiben:
[mm]s = 2^t(2k-1)[/mm].
Wir wollen nun [mm]k=1[/mm] zeigen.
Wendet man wiederum die Aussage
[mm](a+b)|(a^j+b^j)[/mm] für ungerades [mm]j[/mm]
an, diesmal auf [mm]a = n^{2^{2^t}}[/mm], [mm]b=1[/mm] und [mm]j=(2k-1)[/mm] an, so folgt:
[mm](n^{2^{2^t}} + 1) \vert (n^n + 1)[/mm],
d.h. es muss [mm]n^n+1 = n^{2^{2^t}} + 1[/mm]
und damit [mm]n=2^{2^t}[/mm] gelten.
Für [mm]t=0[/mm] und [mm]t=1[/mm] erhalten wir die (schon vorher entdeckt) Primzahl [mm]5[/mm], für [mm]t=2[/mm] die Primzahl [mm]257[/mm],
Für [mm]t=2[/mm] ist bereits (wegen [mm]2^{10}=1024>1000=10^3[/mm]):
[mm]n^n+1 =16^{16}+1 = 2^{64}+1 = 2^4 \cdot 2^{60} + 1 >16 \cdot (10^3)^6+1 > 10 \cdot 10^{18} + 1 > 10^{19}[/mm].
Damit sind alle Primzahlen der Form [mm]n^n+1[/mm], die kleiner als [mm]10^{19}[/mm] sind, gefunden:
[mm]2[/mm], [mm]5[/mm] und [mm]257[/mm].
Für Fragen dazu stehe ich zur Verfügung. 
Liebe Grüße
Stefan
|
|
|
|
