Express as product of primes> 10000000099?

Question

It is supposed to have a factor between 9000 and 10000

Please someone factorize it.

It will be highly appreciated if you can tell me how to get the factors without using computer programs.

The number is 1 followed by 8 zeros then 99

Answer 1

You know the "special" behavior of 9s, 11s and 10^n in decimal? If we work backwards I think we can understand the factorization and generalize this class of numbers.

So the subfactor (23 * 43913)
= 1009999 = 1010000 - 1 = (101 * 10^4) - 1 = 10^6 + 10^4 - 1

and 9901 = (100-1) 10^2 + 1 = (10^4 -10^2 +1)

And the entire factorization was 1009999 * 9901
= (10^6 + 10^4 - 1) * (10^4 -10^2 +1)
expanding it out...
= (10^10 -10^8 +10^6) + (10^8 -10^6 +10^4) - (10^4 -10^2 +1)
and the terms mostly cancel out to
= 10^10 ... -10^2 +1
= 10000000099, voila!

So you are looking at the class of numbers representable by polynomials which only contain terms:
a_i * 10^(2i) where each a_i= either {0,+1,-1}
i.e. basically polynomials Σa_i * x^i where:
x=10^2, and each a_i= either {0,+1,-1}

And the rest is just polynomial factorization of polynomials in x with integer coefficients a_i={0,+1,-1} up to order 5.
Cunningly disguised!

So your factorization above would be written in this polynomial-basis notation as simply {a_i}*{b_i} = {c_i} :
{+1, +1, 0, -1} * {+1, -1, +1} = {+1, 0, 0, 0, +1, -1}
where the basis terms 10^(2i) are implicit.
The rules for multiplying polynomial {a_i} * {b_i} = {c_i} look quite simple, you could crunch it out,
e.g. c3 = a3b0 + a2b1 + a1b2 + a0b3

I humbly submit that's quite neat!

Doing it in reverse is only slightly harder, but we just have to form hypotheses and test them (but by hand, it's not that hard). Most candidate hypotheses won't work, that just means that factorization doesn't work. But for an 11-digit polynomial like you gave, you would only need to test at most 3^5 hypotheses for the intermediate digits (I think you can trim that down, too)
where 3 = number of possibilities for each digit (0,+1, -1).
Loooking back it was also obvious that:
- the leading coefficient of both polynomials must be +1, i.e. a3*b2 = +1 = c5.
- the lowest coefficients must multiply to -1, i.e. a0*b0 = -1 = c0
- and you can define the recurrence relation to require that the coeffts c4..c2 must be 0, and c1 = -1

So you could solve this by solving 6 (slightly non-linear) simultaneous equations on the row vectors {a_i}, {b_i}.
So in fact you don't even need to manually test 3^5 hypotheses.

One last thing: I didn't comment on primeness, only factorizations in general.
Still it's not hard, to tabulate or test whether this class of numbers is prime
Σa_i * 10^(2i) where each a_i= either {0,+1,-1}
You just do the Sieve of Eratosthenes using residue arithmetic, e.g. to test if
9901 = (10^4 -10^2 +1) is prime:
= {+1,-1,+1} in our polynomial basis
it's obviously not divisible by 3,9,11

So to test its residue modulo (say) 13,
note 10 = (13-3):
9901 mod 13 = ((13-3)^4 -(13-3)^2 +1)
= ((-3)^4 -(-3)^2 +1) mod 13
= (81 -9 +1) mod 13

and you can immediately bail out by seeing it's a non-zero number
=> {+1,-1,+1} is not divisible by 13

To fully test 9901 for primeness using the Sieve of Eratosthenes, you need only test prime divisors up to (floor(√9901)) = 99. i.e. test divisibility by the primes 17,19..89,97

Answer 2

The factors of 10000000099 are 23, 9901, and 43913. However, it's certainly not easy at all to figure out the factors of such a large number.

One way is by trial division, whereby you attempt to start from the smallest prime number, attempt to divide and come with no remainder. Of course, this just causes 23 to come out fairly soon, but there is no hope to have more come out.

Factoring, as we know it now, is hard. It's impossible for someone not trained in number theory to even have a chance at fully factoring this by hand in a reasonable amount of time.

Answer 3

Well, I got the same answer as those two geniuses, 23x9901x43913. But I did it the pound my head on a rock way.
I looked up a list of the first 10,000 prime numbers. Then I created an excel spreadsheet that took your number, and divided it by each prime number and put that answer in column B. I took that number, rounded it down in column C, and then I subtracted the two in column D. Then I set conditional formatting for column D to highlight yellow when it is zero, and voila, I had my answer.
I'm no math genius, but I always find a way.

Answer 4

THE PRIME DECOMPOSITION OF 10000000099 IS:

{23, 9901, 43913}

BUT ACCORDING TO THE PREMISE OF YOUR PROBLEM
IT SHOULD BE WITHIN 9000 AND 10000? THEREFORE,
THE PREMISE IS WRONG..