Fermat's little theorem is usually applied to a prime modulus, where every nonzero element is a unit. This is written xp-1 = 1 mod p. Verify that 26 = 64 = 1 mod 7. Similarly, 36 = 729 = 1 mod 7.
Given a large composite integer n, it is usually possible to prove n is not prime by selecting a value of x such that xn-1 is not 1. This is the pseudoprime test. The adjective pseudo is prepended because you might be unlucky in your choices, and repeatedly get 1, even though n is not prime. Pseudo is Greek for false, thus it is possible to get a false result. A number that passes such a test is called a probable prime; it is probably prime.
Some composite numbers, Carmichael numbers, pass the pseudoprime test for every value of x coprime to n. The smallest of these is 561; x560 = 1 for every x, even though 561 is composite. These will be characterized later.
The pseudoprime test is efficient, even for large n, because you need not multiply x by itself a million times to calculate x to the millionth power mod n. Compute x2 mod n, then square this and reduce to get x4, then square this and reduce to get x8, and so on. Write the (large) exponent in binary, and bring in the corresponding power of x wherever a one appears. The following code computes xe mod n.
result = 1;
square = x;
while(e > 0) {
if(e&1) result = result * square mod n; /* least bit of e is set */
square = square * square mod n;
e = e / 2; /* right shift */
}
return result;