Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 5 down vote accepted

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.