11
$\begingroup$

Find all the prime factors of $1,000,027$.

I got all the factors by testing every number from $1$ to $103$:P, 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?

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

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

$\endgroup$
  • $\begingroup$ How did you go from the first to the second step? $\endgroup$ – suomynonA Dec 28 '16 at 6:16
  • $\begingroup$ 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. $\endgroup$ – Ivan Neretin Dec 28 '16 at 6:16
  • $\begingroup$ 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. $\endgroup$ – Bach Dec 28 '16 at 16:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Ivan Neretin Dec 28 '16 at 17:30
  • $\begingroup$ @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. $\endgroup$ – Bach Jan 11 '17 at 23:21
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
4
$\begingroup$

To begin with note that

$1000027 = 100^3 + 3^3 = (100+3)(100^2−3⋅100+32) = 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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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