Es sei ${\displaystyle {}q}$ ein Teiler von ${\displaystyle {}M_{p}=2^{p}-1}$. Dies bedeutet

${\displaystyle {}2^{p}=1\mod q\,.}$

Dann ist ${\displaystyle {}p}$ die Ordnung von ${\displaystyle {}2}$ in ${\displaystyle {}\mathbb {Z} /(q)}$ und nach Lagrange/Fermat ist ${\displaystyle {}p}$ ein Teiler von ${\displaystyle {}q-1}$. Dies bedeutet wiederum

${\displaystyle {}q=1\mod p\,.}$

Da ${\displaystyle {}p}$ und ${\displaystyle {}q}$ ungerade sind, folgt sogar ${\displaystyle {}q=1\mod 2p}$. Wenn ${\displaystyle {}x}$ ein primitives Element von ${\displaystyle {}\mathbb {Z} /(q)}$ ist, so ist ${\displaystyle {}2=x^{{\frac {q-1}{p}}j}}$, da alle Elemente der Ordnung ${\displaystyle {}p}$ sich so schreiben lassen. Da dieser Exponent gerade ist, muss ${\displaystyle {}2}$ ein Quadratrest sein, und der zweite Ergänzungssatz liefert die Kongruenzbedingung modulo ${\displaystyle {}8}$.