# Find all the prime factors of $1000027$

Find all the prime factors of $$1000027$$.

I got all the factors by testing every number from $$1$$ to $$103$$, but when I try to do it using algebra, I get stuck.

My work: $$1000027=(100+3)(100^2-3\cdot100+3^2).$$ How do I simplify further?

Source: Mathematics Magazine, Vol. 23, No. 5, May - Jun., 1950, Problems and Questions.

• Yes, I know the answer already. I am asking how to solve it algebraically. Dec 28, 2016 at 6:06
• I think that the only juicy trick to this problem is identifying the sum of cubes to extract one of the two "big" primes. Dec 28, 2016 at 6:11
• @Moo What I mean is that I want to solve it without so much trial and error; ie solve it using difference of cubes. Dec 28, 2016 at 6:12

## 5 Answers

Go with the sum of cubes and factor out the $103$ thing (which you already did), then notice that $$100^2-3\cdot100+3^2= \\ =100^2+2\cdot3\cdot100+3^2-3\cdot3\cdot100=\\ =(100+3)^2-30^2$$ then factor it as a difference of squares. Then you'll only have to factor $133=7\cdot19$ by hand and verify that everything else is prime.

Come to think of it, this might be an example of Aurifeuillean factorization. Pretty much everybody knows that $x^4+4=(x^2+2x+2)(x^2-2x+2)$. Now we used (rediscovered, if you'd like) a more complicated thing of the same sort: $$x^6+27=(x^2+3)(x^2+3x+3)(x^2-3x+3)$$

• How did you go from the first to the second step? Dec 28, 2016 at 6:16
• Added and subtracted something, plus a little serendipity. OK, to tell the truth, I already knew the answer, and it struck me that $73$ and $133$ must be there for a reason; then I tried to construct some $a^2-b^2$ and succeeded. Dec 28, 2016 at 6:16
• What is the motivation behind this solution if I may ask? That is, how do you go about solving such problems with the kind of approach you have taken.
– Bach
Dec 28, 2016 at 16:31
• @Bach There are no such problems; this is one isolated gem. If you want to look at others remotely related to it, read the link in my answer. As for the motivation, it is simple: for fun. Dec 28, 2016 at 17:30
• @IvanNeretin thanks. Over my years of familiarity with olympiad math problem, I never came across such a question and hence was curious. Makes for a fun addition to my list of rare gems. Thanks.
– Bach
Jan 11, 2017 at 23:21

I think that the only important step is the first one.

If you want to find the prime factors of $73\times 103$ it is going to be tough, because you have to try all primes up to $73$.

On the other hand, once you find the factor $103$, factoring $7\times 19\times 79$ is easy by brute force, because the factors $7$ and $19$ are found really fast, and then proving that $79$ is prime is done quickly also.

First of all we want use $$a^3-b^3=(a+b)(a^2-ab+b^2)$$

we find $1000027=103 \cdot 9709$

then we want to use $a^2-b^2=(a+b)(a-b)$. With a clever observation we see that $$9709=10609-900=(103+30)(103-30)=133\cdot 73$$

that can be factored with ease!

To begin with note that

$$1000027 = 100^3 + 3^3 = (100+3)(100^2−3⋅100+3^2) = 103 \cdot 9709 = 103 \cdot (1001 \cdot 9 + 700) = 103 \cdot 7 \cdot (13 \cdot 11 \cdot 9+100) = 103 \cdot 7 \cdot 1387$$

where we have used the well-known fact that $$1001 = 7 \cdot 11 \cdot 13$$

Then I guess $$1387$$ is small enough to factor by testing cases. Using well-known divisibility rules we can see rather quickly that $$2,3,5,7$$ and $$11$$ are not prime factors of $$1387$$. Also $$13$$ can be dismissed since $$13 \nmid 87$$. Also $$1387 = 1700-313 = 1700 -340 + 27$$, and hence $$17 \nmid 1387$$. Then testing $$19$$ we see that $$1387 = 1900 - 513 = 1900 - 570 + 57$$, and hence $$19 \mid 1387$$.

Then it is straightforward to check that $$1000027 = 7 \cdot 19 \cdot 73 \cdot 103$$

Use the fact that $73 \times 137=10001 = 10^4+1$.

Now, mark off the number in groups of four digits starting from the right, and add the four-digit groups together with alternating signs.

Applying the above rule, $1000027$ in groups of $4$ is $\underbrace{0100}$ $\underbrace{0027}$. Adding the groups with alternate signs gives $73$. Therefore, $1000027$ is divisble by $73$ and gives $13699$ as quotient.

For $13699$ apply the divisbility test by $7$ by marking of the digits in groups of $3s$ by starting from the right and adding together with alternate signs. Therefore, adding the groups $\underbrace{013}$ $\underbrace{699}$ with alternate signs gives $686$ which is divsible by $7$ and hence $13699$ is disvisble by $7$

$13699$ when divided by $7$ gives $1957$.

Now, $1957$ is $1900+57$ and hence is divisible by $19$ giving the quotient as $103$.

Combining them all gives $1000027 = 7\times19\times73\times103$