# Check for prime

I know there are a lot of questions on this board about finding prime numbers, and I've gone through a bunch of them. I even came across this interesting site about primes: http://primes.utm.edu/index.html

The reason I'm making this question is that while looking for some interview questions, I stumbled upon one firm that asked for an interviewee to identify whether 1000001 is prime. The answer is that it is not (divisible by 101 and 9901).

Is there any clever method you could use to figure this out under the time and material constraints of an interview? I looked up a lot of different prime checking ways but none of them seem like something one could perform even with a pen and paper.

Thanks for any help.

-
$x^6+1 = (x^2+1)(x^4-x^2+1)$. – Antonio Vargas May 2 '12 at 5:43
oeis.org/… – pedja May 2 '12 at 6:26

Notice it is $10^6+1$, and $6=2\cdot3$, and recall an algebraic formula...
$$x^3+1=(x+1)(x^2-x+1)$$
$$\implies \frac{10^6+1}{10^2+1}=(10^2)^2-(10^2)+1,$$
which is $9901$. (Implicit polynomial factorizations are often a way to go in these problems.)