0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JMoravitz Nov 1 '16 at 22:24
  • $\begingroup$ @JMoravitz $2003$ iscoprime to $10$, so one only needs ones. $\endgroup$ – Daniel Fischer Nov 1 '16 at 22:27
  • $\begingroup$ 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$ $\endgroup$ – Marios Gretsas Nov 1 '16 at 22:28
  • $\begingroup$ Since $3 \nmid 2003$, you have $2003 \mid 10^n - 1 \iff 2003 \mid \frac{10^n-1}{9}$. $\endgroup$ – Daniel Fischer Nov 1 '16 at 22:28
3
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Note that $2003$ is not divisible by any prime $p<47$ and that $47^2>2003,$ so $2003$ is prime. $\endgroup$ – DanielWainfleet Nov 2 '16 at 22:28
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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} \, . $$

$\endgroup$
  • $\begingroup$ the prime p is 2003? $\endgroup$ – Marios Gretsas Nov 1 '16 at 22:46
  • $\begingroup$ Yes, I wrote $p = 2003$ in the second sentence. $\endgroup$ – André 3000 Nov 1 '16 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.