Editing Lucas primality test (section)

==Example==
For example, take ''n'' = 71. Then ''n''&nbsp;&minus;&nbsp;1 = 70 and the prime factors of 70 are 2, 5 and 7.
We randomly select an ''a=17''&nbsp;<&nbsp;''n''. Now we compute:

:<math>17^{70}\ \equiv\ 1 \pmod {71}.</math>

For all integers ''a'' it is known that

:<math>a^{n - 1}\equiv 1 \pmod{n}\ \text{  if and only if } \text{ ord}(a)|(n-1).</math>

Therefore, the [[multiplicative order]] of 17 (mod 71) is not necessarily 70 because some factor of 70 may also work above. So check 70 divided by its prime factors:

:<math>17^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>

:<math>17^{14}\ \equiv\ 25\ \not\equiv\ 1 \pmod {71}</math>

:<math>17^{10}\ \equiv\ 1\ \equiv\ 1 \pmod {71}.</math>

Unfortunately, we get that 17<sup>10</sup>&equiv;1 (mod 71). So we still don't know if 71 is prime or not.

We try another random ''a'', this time choosing ''a''&nbsp;=&nbsp;11. Now we compute:

:<math>11^{70}\ \equiv\ 1 \pmod {71}.</math>

Again, this does not show that the multiplicative order of 11 (mod 71) is 70 because some factor of 70 may also work. So check 70 divided by its prime factors:

:<math>11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}</math>

:<math>11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}</math>

:<math>11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}.</math>

So the multiplicative order of 11 (mod 71) is 70, and thus 71 is prime.

(To carry out these [[modular exponentiation]]s, one could use a fast exponentiation algorithm like [[Exponentiation by squaring|binary]] or [[addition-chain exponentiation]]).