3
$\begingroup$

I know kind of a very elementary method to factor this number. Consider the following: $$10^6-1 = (10^3-1)(10^3+1)=9 \times 11 \times (10^2+10+1)(10^2-10+1) = 9 \times 11 \times 111\times 91$$ I would then factor each number individually.

Is there a faster method? The great hint is that this number is a rep unit number = $9\ \times 111111$.

$\endgroup$
  • $\begingroup$ In the last line it is $9$ times a rep unit number and you are one $1$ short. $\endgroup$ – Ross Millikan Oct 12 '18 at 15:19
  • $\begingroup$ @RossMillikan what do you mean? do you mean that $10^6 -1 $ is not 11111? $\endgroup$ – Maged Saeed Oct 12 '18 at 15:22
  • 1
    $\begingroup$ You can get to the last step easier if you rewrite it as $10^6-1=999.999= 9\cdot 111.111=9\cdot 11 \cdot 10.101$ $\endgroup$ – Zacky Oct 12 '18 at 15:22
  • $\begingroup$ @RossMillikan just updated it. $\endgroup$ – Maged Saeed Oct 12 '18 at 15:23
  • 1
    $\begingroup$ It is $999,999$, not $111,111$ $\endgroup$ – Ross Millikan Oct 12 '18 at 15:31
5
$\begingroup$

You have gotten as far as the difference of sixth powers will take you. Now $111$ is divisible by $3$ by the sum of digits test, you know $9=3^2,$ and you are down to $3^3\cdot 11 \cdot 37 \cdot 91$. I don't see anything better than trial division at this point. For $37$ you only need to go up to $5$ to see it is prime. For $91$ you need to go to $7,$ you find $91=7\cdot 13$ and you are done. Maybe you know the last two off the top of your head.

$\endgroup$
  • $\begingroup$ Thanks for your clarification. $\endgroup$ – Maged Saeed Oct 12 '18 at 15:20
7
$\begingroup$

\begin{align} 10^6 - 1 &= 1000000-1\\ &= 999999 \\ &= 3^2 \times 111111 \\ &= 3^2 \times 111\times 1001 \\ &= 3^2 \times 111 \times (1100 - 99)\\ &= 3^2 \times 111 \times 11 \times (100-9)\\ &= 3^2 \times 111 \times 11 \times 91 \\ &= 3^2 \times (3 \times 37)\times 11 \times 7 \times 13 \end{align}

$\endgroup$
  • $\begingroup$ Thanks for this brilliancy!! $\endgroup$ – Maged Saeed Oct 12 '18 at 15:25
0
$\begingroup$

If you have a computer, you could use this idea for an algorithm to factor:$$10^n -1 \equiv 0 \mod p \iff 10^n \equiv 1 \mod p$$ This will be more feasible for large values of $n$ because most programming languages have an efficient modular exponentiation function that already exists. If a prime $p$ satisfies this equivalence, it's a prime factor, though you will have to run additional trials to find the degree of $p$.

$\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.