# Fermat's little theorem application

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?

• It is a common exercise to show that there is a number of the form $111\dots11000\dots00$ which is divisible by $k$., but there isn't always a number of the form $111\dots 11$ which is divisible by $k$. For example, no number of the form $111\dots 11$ is divisible by $2$. You are sure that the number must have only ones and no zeroes? – JMoravitz Nov 1 '16 at 22:24
• @JMoravitz $2003$ iscoprime to $10$, so one only needs ones. – Daniel Fischer Nov 1 '16 at 22:27
• but is the number 111...111.000000 is divizible by 2003 for instance the the number 111...111 is also divisible by 2003 becase 2003 does not divide a number of the form $10^n$ – Marios Gretsas Nov 1 '16 at 22:28
• Since $3 \nmid 2003$, you have $2003 \mid 10^n - 1 \iff 2003 \mid \frac{10^n-1}{9}$. – Daniel Fischer Nov 1 '16 at 22:28

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!
• Note that $2003$ is not divisible by any prime $p<47$ and that $47^2>2003,$ so $2003$ is prime. – DanielWainfleet Nov 2 '16 at 22:28
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.
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} \, .$$
• Yes, I wrote $p = 2003$ in the second sentence. – André 3000 Nov 1 '16 at 23:39