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 2p^p 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 2³ + 3² = 17. Somit sind (2, 3) und ( 3, 2 ) Lösungen.

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

2^q + q²

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 q² den Dreierrest 1. q ist ungerade, und so hat 2^q den Dreierrest 2. Es folgt, dass 2^q + q² durch 3 teilbar ist und somit keine Primzahl sein kann.

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