Factoring abominable integers

Algebra Level 4

Consider the number 10000000099. This number has a factor between 9000 and 10000. Find the sum of digits of this factor.

The answer is 19.

1 solution

Patrick Corn
Jan 21, 2015

This number is $x^5+x-1$ where $x = 100$ . It so happens that $x^5+x-1 = (x^2-x+1)(x^3+x^2-1)$ , which leads to $10000000099 = 9901 \cdot 1009999$ . The answer is $\fbox{19}$ .

@Patrick Corn nice solution!

Silas Hundt Staff - 6 years, 4 months ago

Thank you for taking the time to write a solution. But I have seen the same solution elsewhere too. How am I supposed to figure out the factorization of the polynomial? Is there a way to generalize this solution for similar numbers? Or is this just a way to test factorization skills? Thanks once again.

Raghav Vaidyanathan - 6 years, 4 months ago

I don't think there's anything all that generalizable about this situation.

If you plug in a sixth root of unity to $x^5+x-1$ , it's not hard to see that you get $0$ , so $x^2-x+1$ has to be a factor, since it's the sixth cyclotomic polynomial (i.e. the minimal polynomial of $e^{{2\pi i}/6}$ ).

Patrick Corn - 6 years, 4 months ago

Thank you. I read up on cyclotomic polynomials. From what I understand, I think we can say, that if we can find an $n^{th}$ root of unity which satisfies the given polynomial, then the $n^{th}$ cyclotomic polynomial will be one of its factors. Hence, the general approach would be to find that root of unity.

Raghav Vaidyanathan - 6 years, 4 months ago

Factoring abominable integers

The answer is 19.

1 solution

0 pending reports