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 = 2^{x-1} = 3^{x-1} = 5^{x-1} = 7^{x-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