$10^{5000} + 1$ is divisible by which of the following numbers?

Question

The problem went on to give several options where all the numbers were of the form $10^x + 1$.

Let's say $n$ is the number of zeros in such numbers.

Since I couldn't think of any solution I started calculating mods of such numbers with 11, and I observed that if there are even number of zeros ($n$%$2$=$0$) the number is divisible by 11.

similarly for $101$, for every 4th number starting with $n=1$ was divisible by $101$ {$101, 1000001, 1000000000$}.

So I came up with this formula, given that $n, m$ are the number of zeros in two numbers $a,b$ respectively (of the above form), then if ($n-m$) % ($2*m + 2$) = $0$ the $a$ % $b$ = 0.

But I'm not able to prove it.

How do I prove this result?

EDIT: edited the title as complete number is not showing up in superscript.

Answer 1

If a number has $x$ zeroes, it can be written as $10^{x+1}+1$.

You want to show $$2m+2 | n-m \implies 10^{m+1}+1|10^{n+1}+1$$

$$2m+2|n-m \implies 2m+2|n+m+2 \implies 2m+2|2n+2 \implies m+1|n+1$$

Now notice that $\frac{n+1}{m+1}$ must be odd (Why? :))

Then we want to show

$$10^{m+1}+1 | (10^{m+1})^{\frac{n+1}{m+1}}+1$$

$$x+1|x^{\textrm{something odd}}+1$$

Now notice that $x^{\textrm{something odd}}+1$ is always divisible by $x+1$, as $(-1)^{\textrm{odd}}+1=-1+1=0$, and thus by remainder theorem, it is divisible.

Therefore, $2m+2|n-m \implies 10^{m+1}+1 | 10^{n+1}+1$, as desired.

Answer 2

An alternative, should you choose to accept it.

Go back to those choices and look for one of the form $10^n+1$ where $n$ can divide $5000$. And with $n$ containing all powers of $2$ in $5000$. That's probably the right answer. Here's why:

Say that n can divide into $5000$. Then $10^n$ is some root of $10^5000$. Enumerating all the options is tedious cause you're looking at around $20$ options from a square root to a fifth root and so on.

Anyway, rewrite $k=10^n+1$

$10^n=k-1$

$(10^n)^{m}=10^{5000}$ for some integer $m$ that satisfies $mn=5000$.

$10^{5000}+1=(k-1)^m+1$

Let's examine this number $\pmod{k}$, which is what we want to do. If $m$ is odd and only then:

$(k-1)^m \equiv -1 \pmod{k}$

So that would make $10^{5000}+1$ divisible by $10^n+1$. But remember the restriction on $m$.

$nm=2^3 \cdot 5^4$

If $m$ is to be odd then $n$ has to take all the $2$s. This means $n$ is at least $8$ and at most $5000$.

In general, a summary of guaranteed divisors of $10^{5000}+1$:

$10^{8}+1$

$10^{40}+1$

$10^{200}+1$

$10^{1000}+1$

$10^{5000}+1$

$\color{blue}{\text{Q.E.D}}$