Editing Miller–Rabin primality test (section)

=== Proofs ===
Here is a proof that, if ''n'' is a prime, then the only square roots of 1 modulo ''n'' are 1 and −1.
{{math proof|
Certainly 1 and −1, when squared modulo ''n'', always yield 1. It remains to show that there are no other square roots of 1 modulo ''n''. This is a special case, here applied with the [[polynomial]] {{nowrap|X<sup>2</sup> − 1}} over the [[finite field]] {{nowrap|'''Z'''/''n'''''Z'''}}, of the more general fact that a polynomial over some [[field (mathematics)|field]] has no more [[Root of a polynomial|roots]] than its degree (this theorem follows from the existence of an [[Euclidean division of polynomials|Euclidean division for polynomials]]). Here follows a more elementary proof. Suppose that ''x'' is a square root of 1 modulo ''n''. Then:
: <math> (x - 1)(x + 1) = x^2 - 1 \equiv 0 \pmod{n}.</math>
In other words, ''n'' divides the product {{nowrap|(''x'' − 1)(''x'' + 1)}}. By [[Euclid's lemma]], since ''n'' is prime, it divides one of the factors {{nowrap|''x'' − 1}} or {{nowrap|''x'' + 1,}} implying that ''x'' is congruent to either 1 or −1 modulo ''n''.
}}

Here is a proof that, if ''n'' is an odd prime, then it is a strong probable prime to base ''a''.
{{math proof|
If ''n'' is an odd prime and we write {{nowrap|1=''n'' − 1= 2<sup>''s''</sup>''d''}} where ''s'' is a positive integer and ''d'' is an odd positive integer, by Fermat's little theorem:
: <math>a^{2^s d} \equiv 1 \pmod{n}.</math>
Each term of the sequence <math>a^{2^s d}, a^{2^{s-1} d}, \dots, a^{2d}, a^d</math> is a square root of the previous term. Since the first term is congruent to 1, the second term is a square root of 1 modulo ''n''. By the previous [[lemma (mathematics)|lemma]], it is congruent to either 1 or −1 modulo ''n''. If it is congruent to −1, we are done. Otherwise, it is congruent to 1 and we can [[mathematical induction|iterate the reasoning]]. At the end, either one of the terms is congruent to −1, or all of them are congruent to 1, and in particular the last term, ''a''<sup>''d''</sup>, is.
}}