Prove some member of the sequence $7, 77, 777, 7777, \dots$ is divisible by $2019$.

Question

Prove that some member of the sequence $7, 77, 777, 7777, \dots$ is divisible by $2019$.

So far I have figured that as $2019$ is divisible by $3$, then if one of the terms of the sequence $$ a_{n} = 7\left(\frac{10^{n}-1}{9}\right) $$ is divisible by $2019$ it is also divisible by $3$. Hence the number of digits in the solution will be a multiple of $3$, i.e. $777, 777777, 777777777, \dots$

I'm not too sure where to go from here any help would be appreciated.

score 7 · Accepted Answer · answered Oct 05 '20 at 10:04

7

Consider $2020$ terms of the sequence $\{7, 77, 777, \ldots, \underbrace{777...777}_{2020} \}$. Due to pigeonhole principle, at least two of terms have same value by $\mod 2019$: $$ \underbrace{777...777}_a \equiv \underbrace{777...777}_b \equiv x (\bmod 2019). $$ Then (for $a<b$): $$ \underbrace{777...777}_b - \underbrace{777...777}_a = \underbrace{777...777}_{b-a}\underbrace{000...000}_a \equiv 0 (\bmod 2019), $$ hence $$ \underbrace{777...777}_{b-a} \equiv 0 (\bmod 2019), $$ since $GCD(10,2019)=1$.

answered Oct 05 '20 at 10:04

Oleg567

17,295

2

+1 both for elegance and clarity of demonstration – user2661923 Oct 05 '20 at 11:01
2

Amazing thank you for the explanation! – Kit Boothroyd Oct 05 '20 at 12:03
1

This is awesome!!! – Nov 13 '20 at 02:10

score 3 · Answer 2 · answered Oct 05 '20 at 09:57

3

It suffices to find a positive integer $n$ such that $7(\frac{10^{n}-1}{9})$ is divisible by $2019$. So

$$7(\frac{10^{n}-1}{9})\equiv 0\pmod{2019}$$ $$10^{n}\equiv1\pmod{2019}$$

By Euler's theorem we have $10^{\phi(2019)}=10^{1344}\equiv 1\pmod{2019}$, so $n=1344$ will do.

You can also have $n\equiv 0 \pmod{224}$.

answered Oct 05 '20 at 09:57

Alessio K

10,599

+1 elegance : gee, if only you had also used underbraces... – user2661923 Oct 05 '20 at 11:04
Nice one thank you! – Kit Boothroyd Oct 05 '20 at 12:03

score 0 · Answer 3 · answered Mar 14 '21 at 10:55

Inspired by a book titled "A walk through combinatorics" by Miklos Bona on page 2 and page 3.

I prove that an even stronger statement is true, in fact, one of the first 2019 elements of the sequence is divisible by 2019.

I start my proof by assuming that its contrary is true. It means that none of the first 2019 elements is divisible by 2019. When being divided by 2019, their remainders must be in a closed set of $[1,2018]$.
As there are 2018 possible remainders for 2019 elements, there are at least two elements with the same remainder.
Let $A_x$ and $A_y$ (with $x<y$) be the $x$-th and $y$-th elements with the same remainder.
For certain integers $\kappa_x$, $\kappa_y$, and $r$, I can represent $A_x$, $A_y$, and $A_y-A_x$ as follows. \begin{align} A_x &= 2019\kappa_x +r\\ A_y &= 2019\kappa_y +r\\ A_y-A_x&= 2019 (\kappa_y-\kappa_x) \\ \end{align} It means that $A_y-A_x$ is divisible by 2019. It is not the end of proof.
The first $(y-x)$ digits of $A_y-A_x$ are all 7. They are followed by $x$ zeros. Therefore, $A_y-A_x$ can be written as $A_y-A_x=\underbrace{777\cdots777}_{(y-x) \,\text{digits}}\times 10^x$.
As $10^x$ is not divisible by 2019 then $\underbrace{777\cdots777}_{(y-x) \,\text{digits}}$, which is the $(y-x)$-th element of the given sequence, must be divisible by 2019. It is contradictory to my assumption in the beginning.
The proof by contradiction is complete. Some elements of the given sequence are divisible by 2019.

Prove some member of the sequence $7, 77, 777, 7777, \dots$ is divisible by $2019$.

3 Answers3