$10^{5000} + 1$ is divisible by which of the following numbers? 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.
 A: 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.
A: 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}}$
