Wikipedia

Test pierwszości AKS: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m drobne redakcyjne
Linia 7:
 
== Podstawa testu ==
Przy założeniu, że <math>n</math>n≥2 jest liczbą całkowitą, <math>a</math> jest również liczbą całkowitą względnie pierwszą z <math>n</math>, test AKS opiera się na twierdzeniu, że równość:
Test AKS opiera się na równości:
: <math>(x - a)^{n} \equiv (x^{n} - a) \ (\operatorname{mod}\, n)</math>,
która jest prawdziwa wtedy i tylko wtedy, gdy <math>n</math> jest liczbą pierwszą. <math>x</math> należy rozumieć jako formalny symbol (przestrzeń wielomianów). Równość ta jest uogólnieniem [[małe twierdzenie Fermata|małego twierdzenia Fermata]] na wielomiany i można ją łatwo udowodnić korzystając z rozwinięcia:
: <math>(x-a)^n=\sum_{k=0}^n{n \choose k}x^k(-a)^{n-k}</math>
i faktu że:
Źródło: „https://pl.wikipedia.org/wiki/Test_pierwszości_AKS”