Wieder einmal: Rechne mit den Resten!

Aus der Landesrunde der Mathematikolympiade 2011/12

Bestimmen Sie alle Paare (p,q) von Primzahlen derart, dass pq + qp eine Primzahl ist.

Wenn man untersuchen soll, bei welchen Einsetzungen eine Summe von Termen eine Primzahl ergibt, so wird man versuchen, die Summe zu faktorisieren. Ist das wie im vorliegenden Fall schwierig, so wird man Teilbarkeitsregeln zu Hilfe nehmen wollen - Primzahlen sind nur durch 1 und durch sich selbst teilbar. Und immer ist es ratsam, vor Beginn einer systematischen Lösung ein wenig herumzuprobieren.

So sieht man, dass im Fall p = q sich keine Lösung ergeben kann, da 2pp keine Primzahl sein kann, wenn p eine Primzahl ist. Die kleinsten Primzahlen sind 2 und 3; setzt man diese ein, so hat man sogleich einen Treffer, denn 23 + 32 = 17. Somit sind (2, 3) und ( 3, 2 ) Lösungen.

Gibt es weitere Lösungen? Genau einer der beiden Summanden pq und qp muss gerade sein; andernfalls wäre die Summe gerade. Sei dies pq. p ist prim, so muss pq eine Zweierpotenz sein. Unser Problem reduziert sich auf die Frage, ob es Primzahlen der Form

2q + q2

gibt mit q>3 und prim.

Wieder einmal hilft der folgende Satz weiter: Sind r,s die Reste beim Teilen von natürlichen Zahlen m, n durch eine natürliche Zahl q, so hat das Produkt m·n bei Teilung durch q denselben Rest wie das Produkt r·s.
Daraus folgt, dass ein Quadrat nur den Dreierrest 0 oder 1 haben kann; da q>3 und prim, hat q2 den Dreierrest 1. q ist ungerade, und so hat 2q den Dreierrest 2. Es folgt, dass 2q + q2 durch 3 teilbar ist und somit keine Primzahl sein kann.

Nur die Paare (2, 3) und (3, 2) sind Lösungen der Aufgabe.