Für welche Primzahlen  p  ist  2^p + p²  prim ?

Durch Auflistung der Summen für die ersten  p  erkennt man schnell eine Teilbarkeitsregel, die (fast immer) für die Summe gilt. Diese Regel gilt aber nicht für die beiden einzelnen Summanden, sondern bei denen wird man sich die Reste beim Teilen anschauen müssen, um einen Beweis zu finden.

Lösung

Wir schauen uns  2^p + p²  für die Primzahlen  p ≤ 19  an:

 p    2^p + p²
 2       8
 3      17 prim
 5      57
 7     177
11    2169
13    8361
17  131361
19  524649

Für  p = 3  erhält man eine Primzahl, für alle anderen ungeraden Primzahlen  p  ergeben sich für die Summen Vielfache von  3 . Das soll nun bewiesen werden. Einen Hinweis könnten die beiden einzelnen Summanden geben:

 p      2^p   p²
 5      32   25
 7     128   49
11    2048  121
13    8192  169
17  131072  289
19  524288  361

Nun, das ist nicht schwer zu sehen:
-  In der Spalte für  2^p  fehlt immer  1  an einem Vielfachen von  3 ;  2^p  lässt sich also als  3j - 1  schreiben.
-  In der Spalte für  p²  steht stets  1  plus ein Vielfaches von  3 ;  p²  lässt sich also als  3k + 1  schreiben.

Das kann man auch so darstellen:  2^p = 2 mod 3,  p² = 1 mod 3

Warum ist das so?

2^p = 2 mod 3  gilt für alle ungeraden  p , nicht nur für Primzahlen, wie man induktiv nachweist:

Der Induktionsanfang für  p = 1  ist trivial.  -  Ist  2^p = 3j - 1 , so ist  2^p+2 = 4·(3j - 1) = 12j - 4 = 12j - 3 - 1 = 3(4j - 1) - 1 = 3j₁ - 1

Nun zu  p² = 1 mod 3 . Hier wird verwendet, dass  p  prim ist.  -  Wir zeigen, dass  p² - 1  durch  3  teilbar ist:

p² - 1 = (p - 1)(p + 1). Nun sind  p - 1 , p , p + 1  drei aufeinanderfolgende natürliche Zahlen; da  p  als Primzahl nicht durch  3  teilbar ist, muss entweder  p - 1  oder  p + 1  durch  3  teilbar sein.


3  ist die einzige Primzahl  p ,  für die  2^p + p²  prim ist.
Alle anderen  2^p + p²  mit  p > 3  sind durch  3  teilbar.


Dieses Problem entstammt der hervorragenden und sehr empfehlenswerten Website Mathematical Excalibur, die vom Department of Mathematics der Hong Kong University of Science and Technology herausgegeben wird. Unser Primzahlenproblem findet man in Ausgabe 3/3, Problem 56.  -  Es werden auf dieser Problem-Seite von Zeit zu Zeit noch einige weitere Excalibur-Probleme erscheinen.

Publiziert 2017-12-31          Stand 2016-12-26

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem