What is the sum of the first two prime numbers which divide Googol + 1

Number Theory Level 4

A googol is equal to $10^{100}$ .

What is the sum of the smallest 2 prime numbers that divides "googol plus one"?

Hint: The largest prime factor of the number 123456787654321 is the second prime number which divides Googol + 1

The answer is 210.

1 solution

Vijay Simha
Feb 22, 2017

The polynomial X^m+1 is divisible by the polynomial X+1, when m is odd

This means that whatever positive integer you substitute for X in X^m+1 when m is odd, the result will be divisible by X+1. Hence, X^m+1 cannot be prime (unless m=1 or you've substituted 1 for X, in which case the divisor we found, X+1, is the same as the number X^m+1).

This explains why 2^5+1=33 is divisible by 2+1=3

This is why 10^3+1=1001 is divisible by 10+1=11

This is why 77^77+1 is divisible by 77+1=78.

We don't even need to calculate that big number to the left, we already know it's divisible by 78.

Now, all we need to do is take m=25 (which is odd) and X=10^4 to find that

(10^4)^25 +1 is divisible by 10^4+1

So Googol+1 is divisible by 10,001. It is not a prime number.

10001 is itself equal to 73 x 137, 73 is the smallest prime number which divides Googol and 137 is the next prime number which divides it.

Note that the first line requires $m$ is odd (which was only stated in the second paragraph). Writing it in the first paragraph would make it easier for others to follow what you are saying.

As always, to prove that this is the minimium, we have to
1. Show that it is attained
2. Show that no smaller value works

While you've offered proof that 73 and 137 divide $10 ^ { 100 } + 1$ , why can't if have any smaller factors? As an explicit counter example, the smallest prime factor of $12^3 + 1$ isn't $12 + 1 = 13$ , but is 7.

It turns out that 73 and 137 are indeed the 2 smallest prime factors of $10 ^ {100} + 1$ , so the numerical answer is correct.

Calvin Lin Staff - 4 years, 3 months ago

What is the sum of the first two prime numbers which divide Googol + 1

The answer is 210.

1 solution

0 pending reports