Revision history [back]

Yes, checking that a number is not prime can be very easy, without factoring it: you just check that it does not satisfy some condition that all primes satisfy.

For example, if $n$ is a prime, then for any integer $a$, we have $a^n$ is congruent to $a$ modulo $n$.

Another way to say that is that if $n$ is an integer, and if there is any integer $a$ such that $a^n$ is not congruent to $a$ modulo $n$, then $n$ is not prime. Finding such an $a$ can be very cheap but it would not give a way to factor $n$.

See the notion of probable prime and pseudo-prime.