Show that there is a number consisting only of 1’s that is divisible by 2001.
ie, we have to prove 2001 divides $1+10+10^2+10^3+...+10^k$ for some $k$,
How can we proceed now?
$\begingroup$ $\endgroup$
4 
- $\begingroup$ Hint: Consider the set of all such numbers modulo 2001. $\endgroup$user211599– user2115992019-06-23 02:02:13 +00:00Commented Jun 23, 2019 at 2:02
- $\begingroup$ Possibly useful: the sum is $(10^{k+1} -1)/9$. $\endgroup$Ethan Bolker– Ethan Bolker2019-06-23 02:03:49 +00:00Commented Jun 23, 2019 at 2:03
- 1$\begingroup$ $(10^{3\phi(2001)}-1)/9$ $\endgroup$J. W. Tanner– J. W. Tanner2019-06-23 02:07:22 +00:00Commented Jun 23, 2019 at 2:07
- 1$\begingroup$ math.stackexchange.com/questions/1009511/… $\endgroup$lab bhattacharjee– lab bhattacharjee2019-06-23 02:23:13 +00:00Commented Jun 23, 2019 at 2:23
Add a comment |
4 Answers
$\begingroup$ $\endgroup$
Consider the set $S = \{1, 11, 111, 1111, \ldots \}$. By the Pigeonhole Principle, two of these numbers must be equal modulo $2001$. Subtracting yields a number divisible by $2001$ of the form $10^k s$, where $s \in S$. But $\gcd(10, 2001) = 1$, so $2001 \mid s$.
$\begingroup$ $\endgroup$
3 By Euler's theorem, $2001|10^{\phi(2001)}-1$.
Since $2001=3\times23\times29, \phi(2001)=2\times22\times28=1232.$
Therefore $\dfrac{2001} 3=23\times29=667|\dfrac{10^{\phi(2001)}-1}9, $ so $2001=3\times667 |\dfrac{10^{3\phi(2001)}-1}9. $
- $\begingroup$ so the number with $3696$ $1$s is divisible by $2001$ $\endgroup$J. W. Tanner– J. W. Tanner2019-06-23 02:20:20 +00:00Commented Jun 23, 2019 at 2:20
- $\begingroup$ Could you explain the last step? $\endgroup$user403337– user4033372019-06-23 03:06:47 +00:00Commented Jun 23, 2019 at 3:06
- $\begingroup$ @ChrisCuster: sorry if wasn't clear; does this help? If $a\equiv1\pmod9$ then also $a\equiv1\pmod3$ so $3|a^2+a+1$ so $27|a^3-1=(a-1)(a^2+a+1)$ ; use that with $a=10^{\phi(2001)}$ $\endgroup$J. W. Tanner– J. W. Tanner2019-06-23 03:43:28 +00:00Commented Jun 23, 2019 at 3:43
$\begingroup$ $\endgroup$
First, we have
$$2001 = (3)(23)(29).$$
Now, let $R_{n} = \frac{10^{n} - 1}{9}$ denote the $nth$ repunit.
Since $3 | R_{3}, \, 23 | R_{22},$ and $29 | R_{28}$, and
Because $LCM(3, 22, 28) = 924$, it follows that
$$2001 \, | \, R_{924} = \frac{10^{924} - 1}{9}.$$
$\begingroup$ $\endgroup$
$2001=3\cdot 23\cdot 29$, and $23\cdot 29$ is a divisor of $10^{\text{lcm}(22,28)}-1=10^{308}-1$.
It follows that $2001$ is a divisor of $\frac{10^{924}-1}{9}$, which is a number made by $924$ digits equal to $9$.
As an alternative, the sequence defined by $$ a_0 = 0, \qquad a_{n+1} = 10 a_n+1 $$ is periodic $\!\!\pmod{m}$ for any $m$, see here. In particular there is some $k\in[1,2001]$ such that $a_k\equiv a_0\equiv 0\pmod{2001}$.
