Mersenne-Zahlen/Primteiler/Kongruenzbedingungen/Fakt/Beweis

Beweis

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

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

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

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

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

Zur bewiesenen Aussage