Lucas primality test

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

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'' − 1, which means that the order of that group is ''n''−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''')*| = ''n''−1 and both equivalences will hold for any such primitive root.

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'' − 1, which means that the order of that group is ''n'' − ;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''')*| = ''n''−1 and both equivalences will hold for any such primitive root.

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

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