Editing Lucas primality test (section)

==Concepts==
Let ''n'' be a positive integer.  If  there exists an integer ''a'', 1&nbsp;<&nbsp;''a''&nbsp;<&nbsp;''n'', such that

:<math>a^{n-1}\ \equiv\ 1 \pmod n \, </math>

and for every prime factor ''q'' of ''n''&nbsp;&minus;&nbsp;1

:<math>a^{({n-1})/q}\ \not\equiv\ 1 \pmod n \, </math>

then ''n'' is prime. If no such number ''a'' exists, then ''n'' is either 1, 2, or [[composite number|composite]].

The reason for the correctness of this claim is as follows: if the first equivalence holds for ''a'', we can deduce that ''a'' and ''n'' are [[coprime#Properties|coprime]]. If ''a'' also survives the second step, then the [[Order (group theory)|order]] of ''a'' in the [[Group (mathematics)|group]] ('''Z'''/''n'''''Z''')* is equal to ''n''&minus;1, which means that the order of that group  is ''n''&minus;1 (because the order of every element of a group divides the order of the group), implying that ''n'' is [[Prime number|prime]]. Conversely, if ''n'' is prime, then there exists a [[primitive root modulo n|primitive root modulo ''n'']], or [[generating set of a group|generator]] of the group ('''Z'''/''n'''''Z''')*. Such a generator has order |('''Z'''/''n'''''Z''')*|&nbsp;=&nbsp;''n''&minus;1 and both equivalences will hold for any such primitive root.

Note that if there exists an ''a''&nbsp;<&nbsp;''n'' such that the first equivalence fails, ''a'' is called a [[Fermat primality test#Concept|Fermat witness]] for the compositeness of ''n''.