Fermat's little theorem application

Question

Prove that there exists a number of the form $\sum\limits_{n=0}^N 10^n=1111....11 $ (a sequence of $N+1$ digits 1) which is divisible by $2003$.

I found a proof of this exercise which uses the pigeonhole principle, but I would like to see if it can be proved using Fermat's little theorem, assuming that there does not exist such a number, deriving a contradiction (actually this is the way I tried).

Is it possible to prove this simply by contradiction (if Fermat's little theorem does not give a solution)?

If it is, can someone give me a hint?

Thank you in advance!

Answer 1

First, to make things simpler, we have the following: $$\sum_{n=0}^N 10^n=\frac{10^{N+1}-1}{9}$$ Thus, we want to find: $$\frac{10^{N+1}-1}{9} \equiv 0 \pmod {2003}$$ Now, fractions in modular equations can be tricky, so we have to be careful here. Luckily, $9$ is coprime to $2003$ and therefore $9^{-1} \pmod {2003}$ is a thing, so get rid of the fraction: $$(10^{N+1}-1)(9^{-1}) \equiv 0 \pmod {2003}$$ Multiply both sides by $9$ and add both sides by $1$: $$10^{N+1} \equiv 1 \pmod {2003}$$ Now, can you try to apply Fermat's Theorem to find $N$? Good luck!

Answer 2

To get started, observe that a desired $R_N:=\sum_{n=0}^N 10^n$ is divisible by $2003$ if and only if $9R_N = (10^{N+1}-1)$ is also divisible by $2003$.

This means that we require $N$ such that $10^{N+1} \equiv 1 \bmod 2003$. Apply Fermat's Little Theorem.

Answer 3

Using the formula for a finite geometric series, we have $$ \sum_{n=0}^N 10^n = \frac{1 - 10^{N+1}}{1 - 10} = \frac{10^{N+1} -1}{9} \, . $$ Since $p = 2003$ is prime, then $9$ is invertible mod $p$, so it suffices to find $N$ such that $10^{N+1} - 1 \equiv 0 \pmod{2003}$. By Fermat's little theorem, $a^{p-1} \equiv 1 \pmod{p}$ for any $a$ with $\gcd(a,p) = 1$. Then taking $N = p-2 = 2001$ should work: $$ 10^{p-2+1} - 1 = 10^{p-1} - 1 \equiv 1 - 1 = 0 \pmod{p} \, . $$