Lucas's Primality Test With Factored N-1

Fermat's Little Theorem assures us that if N is a prime then 

                b^(N-1) = 1   (mod N)                        (1)

for every integer b coprime to N.  In contrast, if N is composite it is
quite rare for the above congruence to be satisfied for ANY b.  This
fact enables us to test for compositeness quite easily, simply by
checking to see if b^(N-1) is congruent to 1 (mod N) for some particular
value of b.  However, although this congruence is necessary for
primality, it isn't quite sufficient, because for any given base b
there exist composites N that satisfy (1). Such integers are called
pseudoprimes to the base b.  In fact, there exist composite integers
that are pseudoprimes to every base with which they share no common
factor.  Such composites are called Carmichael numbers, the smallest
of which is 561.

Euler generalized Fermat's theorem by showing that for ANY integer N,
prime or composite, we have  

               b^phi(N) = 1   (mod N)                       (2)

for any integer b coprime to N, where phi(N) is Euler's totient
function, representing the number of positive integers less than
and coprime to N.  Obviously if N is a prime then phi(N) = N-1, in
which case Euler's theorem reduces to Fermat's.

Edouard Lucas noticed that Euler's theorem enables us to definitely
determine the primality of N fairly easily if we know the factorization
of N-1.  The basic idea of this test is the foundation for virtually 
all deterministic primality tests, so it's worthwhile to understand
exactly how it works.

Suppose we examine the residues (mod N) of the sequence 

       1   b   b^2   b^3   b^4   b^5 ....

Let T denote the smallest exponent such that b^T = 1 (mod N).  This
implies that b^k can be congruent to 1 (mod N) only if k is a multiple
of T.  We can call T the fundamental period of the sequence modulo N.
Also, from Euler's theorem we know that  b^phi(N) = 1 (mod N), so
clearly phi(N) is a multiple of T.  Thus we can write phi(N) = mT
for some integer m.

Now, suppose we have determined by calculation that the number N 
satisfies Fermat's condition for primality with respect to the base 
b.  In other words, we have found that

               b^(N-1)  =  1    (mod N)

It follows that N-1 must be a multiple of the fundamental period T,
so we can write N-1 = nT for some integer n.  Thus we know that the
fundamental period T divides both phi(N) and (N-1).  Of course, we
also know that phi(N) is less than or equal to N-1.  Therefore, if
we could prove that the fundamental period T equals N-1, then it 
would follow that phi(N) equals N-1, which can only be the case if 
N is a prime.

But how can we prove that T = N-1?  Well, we know that N-1 = nT for
some integer n, which means that n divides N-1.  Assuming n is greater
than 1, let p denote any prime divisor of n.  It follows that p is
also a prime divisor of N-1, and we must have

               b^((N-1)/p) = 1     (mod N)

On the other hand, suppose we examine b^((N-1)/q) for EVERY prime
divisor q of N-1 and we find that none of those values is congruent
to 1 (mod N).  This can only mean that n=1, which means the fundamental
period T equals N-1, and therefore phi(N) equals N-1 (because T divides
phi(N), and phi(N) is less than or equal to N-1).

This proves Lucas's primality criterion:

    If, for some integer b, the quantity b^(N-1) is congruent to 1
    modulo N, and if b^((N-1)/q) is NOT congruent to 1 modulo N for
    ANY prime divisor q of N-1, then N is a prime.

Of course, this all just amounts to the assertion that if we can find
an element b  whose "order" mod N is N-1, then N is a prime.  Such
a number is called a "primitive root" mod N.  If N is a prime there are
phi(N-1) primitive roots modulo N, so we are assured of the existence
of this many values of b that would be suitable to prove the primality
of N via Lucas's test.