If a^(n-1) mod n != 1, the number is composite and can be rejected. But, if a^(n-1) mod n == 1, you can only be 50% sure n is prime.
I should point out that the standard argument that picking 'k' different values for 'a' and then calculating the probability as (1/2)^k is fallacious. This would be true if the probabilities were independent, but they aren't. There was a paper on this about five years ago whose awareness has not been yet widespread. I no longer have the reference. For everybody that wants to really know about this, find out about the Miller-Rabin test.
(Roughly speaking; Phil Karn notes that the PGP docs indicate a 50%, I've seen proofs that this pseudoprime test fails 50% of the time, etc. But these are upper bounds; the real percentage seems much lower and I haven't seen a tighter bound on it).
The 50% figure is easy to show with some considerations about quadratic residues. Tightening the bound is much more difficult. Eric