The encryption program PGP takes advantage of this property of the theorem to test whether the large random numbers it selects are prime. It tests the values we'll call x using 4 values of a (referred to as witnesses) using the above formula. These 4 values are 2, 3, 5 and 7, the first four primes. If 1 = 2x-1 = 3x-1 = 5x-1 = 7x-1 (mod x), it knows that the number x is probably prime. If any of the equations comes up with a value other than 1, then x is definitely composite. Using additional witnesses decreases the chance that a composite x will appear to be prime, although very few large numbers can fool the 4 witnesses already listed.
The pseudoprime article gives an in-depth discussion of numbers which fool primality tests such as these.\n