Test Fermata na liczbę pierwszą, użyteczność bazy n-1

[gszpetkowski]

W o liczbach pierwszych trafiłem na algorytm służący do sprawdzania, czy dana liczba jest (pseudo)pierwsza w oparciu o małe twierdzenie Fermata w postaci:

\(\displaystyle{ a^{n-1}\equiv 1 \pmod{n}}\) (3.3)

Autorzy twierdzą, że nie ma sensu brać bazy \(\displaystyle{ a = n-1}\), gdyż dla takiej wartości powyższa kongruencja jest zawsze prawdziwa w przypadku, gdy \(\displaystyle{ n}\) jest liczbą nieparzystą (a tylko takie zamierzam poddawać testowaniu). Innymi słowy zachodzi relacja:

\(\displaystyle{ (n-1)^{n-1}\equiv 1 \pmod{n}}\)

Sprawdziłem empirycznie dla kilku wartości i rzeczywiście tak jest, ale czy mógłbym prosić nakierowanie, lub podanie dowodu (najlepiej ogólnego dla liczb nieparzystych) ?

[JakimPL]

Niech \(\displaystyle{ n=2k-1}\). Wówczas, wychodząc z tożsamości:

\(\displaystyle{ 2k-2 \equiv 2k-2 \pmod{ 2k-1}\\
2k-2 \equiv (2k-1)-1 \pmod{ 2k-1}\\
2k-2 \equiv -1 \pmod{ 2k-1}}\)

Mogę podnieść obie strony do potęgi \(\displaystyle{ n-1=2k-2}\):

\(\displaystyle{ (2k-2)^{2k-2} \equiv (-1)^{2k-2} \pmod{ 2k-1}\\
(2k-2)^{2k-2} \equiv 1 \pmod{ 2k-1}\\
(n-1)^{n-1} \equiv 1 \pmod{n}}\)

[gszpetkowski]

Dziękuję bardzo Z mojej strony temat można zamknąć.