PRIM hoch prim

Gesucht sind alle Primzahlen p und q, für die

p^q + q^p

wieder eine Primzahl ist.

Wären p und q beide ungerade, so wäre auch jeder Summand der Summe p^q + q^p ungerade und damit die ganze Summe gerade. Weil sie außerdem größer ist als 2, kann sie keine Primzahl sein.
Man erhält also bestenfalls dann eine Primzahl, wenn eine der Zahlen p oder q die 2 ist.
Es soll p = 2 sein.

Für p = 2 und q = 3 ist p^q + q^p eine Primzahl. Die Tabelle führt uns zu der Vermutung, dass alle weiteren Summen den Teiler 3 haben. Das ist auch so und es soll jetzt bewiesen werden.

Die Dreierreste von q²

Ist q eine Primzahl größer als 3, so ist sie ungerade und als Rest beim Teilen durch 3  kommen nur 1 und 2 in Frage.

Fall 1:

Fall 2:

Die Dreierreste von Zweierpotenzen

2¹ = 2 hat den Dreierrest 2
2² = 4 hat den Dreierrest 1
2³ = 8 hat den Dreierrest 2
2⁴ = 16 hat den Dreierrest 1
Das geht immer so weiter (das Beweisverfahren, mit dem man das einwandfrei beweisen kann, heißt vollständige Induktion).
Wir entnehmen speziell: Für ungerade Exponenten q hat 2^q den Dreierrest 2.

Die Dreierreste der Summe 2^q + q²

Dass 2^q den Dreierrest 2 hat, heißt:

Es gibt eine natürliche Zahl n, so dass 2^q = n · 3 + 2.

Dass q² den Dreierrest 1 hat, heißt entsprechend:

Es gibt eine natürliche Zahl m, so dass  q² = m · 3 + 1.

Nimmt man das zusammen, so erhält man:

2^q + q² = n · 3 + 2 + m · 3 + 1 = (n + m) · 3 + 2 + 1 = (n + m) · 3 + 3 = (n + m + 1) · 3 ,

d. h.  2^q + q² ist durch 3 teilbar, wenn q eine Primzahl größer als 3 ist.

Zusammenfassung:

Genau eine der Primzahlen muss 2 sein, weil sonst die Summe gerade wäre. Die andere muss 3 sein, weil sonst die Summe durch 3 teilbar wäre.
Damit ist 17 die einzige Primzahl, die als Summe der Form p^q + q^p mit Primzahlen p und q darstellbar ist.