Test Fermata na liczbę pierwszą, użyteczność bazy n-1
: 25 lis 2013, o 20:54
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) ?
\(\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) ?