Let 
be an odd prime, 
be an integer such that 
and 
, and
 |
Then the following are equivalent
1. 
is prime.
2. There exists an 
such that 
,
where GCD is the greatest common divisor (i.e., 
and 
are relatively prime). This is a modified version
of the original theorem due to Lehmer.
