The sequence of integers $1, 11, 111, 1111, \ldots$ have two elements whose difference is divisible by $2017$

Question

Prove that the sequence $\{1, 11, 111, 1111, .\ldots\}$ will contain two numbers whose difference is a multiple of $2017$.

I have been computing some of the immediate multiples of $2017$ to see how their congruence classes look like, but I am not really sure where that is taking me. All I know right now is that the difference will have the form $11\ldots1100\ldots 00$ and that the difference: $(a-b)\mod 2017=0$ where $a,b$ belong to the sequence.

Answer 1

The key here is that there are infinite numbers. Using the pigeonhole principle you can see that there should two numbers when divided by 2017 give the same residue and conclude.

Answer 2

While the right way to do this problem is to use the pigeonhole principle, one may be curious as to find a specific number that works:
That is to write an algorithm that will find it, given the numbers involved might get big.
It turns out this is not overly difficult, here is the result:

If $a= \\ 550873133917258855285627719936098716465597972786867184487412548889990635156723\\ 406599460144328761086321820084834462623257863713986668870159202335702087809177\\ 546411061532529058557814135404616316862226629207293560293064507243981711011953\\ 947006004517159698121522613342147303476009475017903376852310912796782900897923\\ 208285131934115573183495840907838924695642593510714482454690684735305459152757\\ 120035255880570704566738280174075910317853798270258359499807194403128959400650\\ 030298022365449237040709524596485429405607888503277695146807690188949484933619\\ 787362970307938081859747700104665895444279182504269266787858756128463614829504\\ 765052608384289098220679777447253897427422464606401145816118547898418994105657\\ 467085330248443783396683743733818101691180521125984685726877100203823059549385\\ 776455682256376356525092271249931140858260342643089296535007987660441800253401\\ 641601939073431388751170605409574175067481958904864209772489395692172092767035\\ 751666391230099708037239023852806698617308433867680273233074422960392221671349\\ 088304963366936594502286123505756624249435355037734809673332231587065498815622\\ 762077893461135900402137387759598964358508235553352063019886520134413044675811\\ 160689693163664408086817605905359995593014928661929157714978240511210268275216\\ 217705062524100699608880074918746212747204318845369911309425439321324299013937\\ 090288106649038726381314383297526579628711507739767531537486916763069465102186\\ 966341651517655483942048146311904368423951963862722415027819093262821572191924\\ 199856772985181512697625736792816614333718944527075414532033272737288602434859\\ 251914284140362474522117556326777943039717952955434363466093758607392717457169\\ 613837933124001542444774968324794799757615821076406103674323803228116564755136\\ 891973778438825538478488404120531041701096237536495345122018399162672836445766\\ 539965845865697129950972291081363961879579132925687214234561780421968820580620\\ 283148790833471051616812648047154740263317358012449732826530050129455186470555\\ 83099212251418498319836941552360491378835454194898914779926183 $

then $b=a\cdot2017=111\cdots11$, total of $2016$ digits $1$'s (and no other digits).

Hence $(10\cdot a)\cdot2017=10\cdot b=111\cdots110$, total of $2016$ digits $1$'s followed by a $0$,
that is $(10\cdot a)\cdot2017=111\cdots111-1$ where the $111\cdots111$ has $2017$ digits $1$'s.

The informal description of the algorithm follows.
Starting with $2017$ we need to multiply by $3$ to make the last digit $1$:
$2017\cdot3=6051$.
Then we want to keep the last $1$ and turn the second last $5$ into $1$.
We know $5+6=11$ and $7\cdot8=56$, hence we multiply $2017\cdot80=161360$ and add this to $6051$ to obtain $167411$.
Now we need to fix the third-last digit which is $4$. Since $4+7=11$, this time we need to multiply $2017\cdot1\cdot10^2=201700$ and add this to $167411$, to obtain $2017\cdot183=369111$, which is three correct digits $1$'s at the end. We know that if we do this for long enough then (by pigeonhole principle) we need to get a number consisting of digits $1$ only (called a repunit), and this takes a second or two on a computer. I used the function $f(c)$ where $c$ is the "digit to be corrected", that is, we multiply $2017$ by $f(c)\cdot10^k$ (where $k$ gradually increases), where $f(0)=3$, $f(1)=0$, $f(2)=7$, $f(3)=4$, $f(4)=1$, $f(5)=8$, $f(6)=5$, $f(7)=2$, $f(8)=9$, $f(9)=6$. This $f$ has the property that $c+f(c)\cdot7$ ends in $1$ for $c=0,1,\cdots,9$.

Edit. After doing the above the long way I realize the comment by @Phicar (after the OP) shows a shorter way to do this, using Fermat's Little Theorem. In particular the number $a=5508\cdots183$ that I came up with above is exactly $a=\displaystyle(\frac{10^{2017-1}-1}{10-1})/2017=(\frac{10^{2016}-1}9)/2017$. One may find a lot more online, google repunit factorization, gives results on Wikipedia, MathWorld, some papers in pdf by Snyder 1982, Jaroma 2007, and a discussion at https://mathlesstraveled.com/2011/11/17/fun-with-repunit-divisors-more-solutions/ (by Dr. Brent Yorgey).

I have to think how the algorithm described above relates to Fermat's Little Theorem. I believe the algorithm would work for any number $k$ (not necessarily a prime) that is not a multiple of $2$ or $5$, to produce a repunit divisible by $k$, I wonder how many "steps" it might take, in terms of the factors of $k$.

Edit. There are at least six other MSE questions (some pretty old) discussing this topic. Broadly, the answers are of two types: Either just using the pigeon-hole principle, or, alternatively, trying to be more specific and come up with a particular repunit that is a multiple of the number in question. The latter may involve Fermat's Little Theorem, or some algorithmic approach. Here are links to some of these questions, for reference (older questions first, and without emphasizing any particular answers). (I surely must have overlooked some, please feel free to add more links in a comment.)

Priyank Bhatnagar (https://math.stackexchange.com/users/19802/priyank-bhatnagar), A natural number multiplied by some integer results in a number with only ones and zeros, URL (version: 2015-04-25): A natural number multiplied by some integer results in a number with only ones and zeros

Eight (https://math.stackexchange.com/users/20036/eight), Prove that every number ending in a $3$ has a multiple which consists only of ones., URL (version: 2012-07-01): Prove that every number ending in a $3$ has a multiple which consists only of ones.

HowardRoark (https://math.stackexchange.com/users/32668/howardroark), All odd primes except $5$ divide a number made up of all $1$s, URL (version: 2012-07-01): All odd primes except $5$ divide a number made up of all $1$s

user1526710 (https://math.stackexchange.com/users/43178/user1526710), Divisibility and Pigeonhole principle, URL (version: 2012-09-30): Divisibility and Pigeonhole principle

limp_chimp (https://math.stackexchange.com/users/44186/limp-chimp), Prove that every integer $n>0$ with $\gcd(n,10) = 1$ has a multiple that can be written with only the digit $9$., URL (version: 2012-11-04): Prove that every integer $n>0$ with $\gcd(n,10) = 1$ has a multiple that can be written with only the digit $9$.

user2993422 (https://math.stackexchange.com/users/212041/user2993422), prove that there are infinitely many numbers of the form $x = 111....1$ such that $31|x$, URL (version: 2015-06-13): prove that there are infinitely many numbers of the form $x = 111....1$ such that $31|x$

Answer 3

111....111 - 11111....111 = 1111....11000....000 = 1111...1*$10^m$.

$\gcd (2017, 10^m) = 1$

So the statement is equivalent to showing $2017|1111....1$ for some 1111....1.

2017 is prime.

So it suffices to show $p|111....1$ for some 1111..11 for each prime $p$.

$10^{p-1}\equiv 1 \mod p$ by Fermat's little theorem. So $p|10^{p-1}- 1.

Now $(10^{p-1} - 1)/(10 - 1) = \sum_{j=0}^{p-2} 10^i$ = 1111....1 with $p-1$ 1s.

So $p|\frac{10^{p-1} - 1}{10 -1}*9$. If $p \ne 3$ the $\gcd(p,9) =1$ and $p|\frac{10^{p-1} - 1}{10 -1}$. (If $p = 3$ then $3|111$.)

So $2017|(10^{2016} - 1)/9$ which is 2016 1s.

So.... N = 111111111...1111 with with $k > 2016$ 1s and M = 11111....111 with $k - 2016$ 1s. is such that N-M = 111....1111000.....0 which has 2016 1s and k-2016 0s. This is divisible by 1111....1111 with 2016 0s which is divisible by 2017.