For every positive integer $k$ not divisible by $101$ there exists $n$ such that the sum $1+k+k^2+...+k^n$ is divisible by 101

Question

I can write the sum using geometric series as $\frac{k^{n+1} - 1}{k-1}$ but I'm not sure how to continue from here. I've tried using induction but I got stuck.

Answer 1

You mention in your tags the pigenhole-principle. This is a way to solve this. In the comments Peter pointed out, that the statement fails when $k$ is divisible by $101$.

Observe for every $n$ the remainder modulo $101$. If you get the remainder $0$ then you are done. If you do not get it, then you can just calculate arbitrary many $n$ values. At most 101.

After that you have to get a remainder which we already had. Then you have for some $m$ and $n$ that

$\sum_{i=0}^n k^i\mod 101\equiv\sum_{i=0}^m k^i\mod 101$.

Without loss of generality $m>n$, and we have after subtraction

$\sum_{i=n+1}^{m} k^{i}\equiv 0\mod 101$. Hence divisibility by 101.

So you have $k^{n+1}+\dotso +k^m=k^{n+1}(1+k+\dotso +k^{m-(n-1)})$.

As $101$ is prime, and $101\nmid k$, we have $101\nmid k^{n+1}$. Hence

$101\mid 1+k+\dotso +k^{m-n+1}$