Let n be a positive integer, and let k be the number of integers < n that are relatively prime to n.
Show that n is prime if and only if k = n-1.
Note that what this is really saying is that $\displaystyle n$ has exactly two divisors. And since $\displaystyle 1,n$ are always divisors of $\displaystyle n$ we may conclude that they are the only divisors. But that is the defintion of primeness, that only the number itself and one are positive divisors.