$2018$ as a multiple of $2019$

Number Theory Level 2

Is there a number in the form $\underbrace{2018201820182018...2018}_{\text{\$n\$ times}}$ with $2018$ repeating $n$ times that is a multiple of $2019?$

Yes No

1 solution

Victor Paes Plinio
Jun 30, 2018

Let $X_n =\underbrace{2018201820182018...2018}_{\text{\$n\$ times}}$ . Observe the following list of $X_n$ numbers:

$X_1=\underbrace{2018}_{\text{1 times}}$

$X_2=\underbrace{2018201820182018...2018}_{\text{2 times}}$

$X_3=\underbrace{2018201820182018...2018}_{\text{3 times}}$

$...$

$X_{2020}=\underbrace{2018201820182018...2018}_{\text{2020 times}}$

$...$

In the division by $2019$ there are $2019$ possible remainders. In the list above we have $2020$ numbers. By the Pigeonhole Principle there are two numbers, $X_i$ and $X_j$ , with $X_i < X_j$ , that leave the same remainder in the division by $2019$ . It means that the difference between these two numbers is a multiple of $2019$ :

$X_j - X_i = \underbrace{2018...2018}_{\text{\$j\$ times}}-\underbrace{2018...2018}_{\text{\$i\$ times}}=\underbrace{2018...2018}_{\text{\$j-i\$ times}}\underbrace{000000..0000}_{\text{\$4i\$ times}}$

$X_n =\underbrace{2018...2018}_{\text{\$j-i\$ times}}\underbrace{000000..0000}_{\text{\$4i\$ times}}=\underbrace{2018...2018}_{\text{\$j-i\$ times}}\times {10}^{4i}=\boxed{X_{j-i}\times {10}^{4i}}$

The boxed number must be a multiple of $2019$ . The part ${10}^{4i}$ isn't a multiple of $2019$ , so the part $X_{j-i}=\underbrace{2018...2018}_{\text{\$j-i\$ times}}$ must be a multiple of $2019$ .

Hence, the answer for this question is YES , there is a number in the form $\underbrace{2018201820182018...2018}_{\text{\$n\$ times}}$ that is a multiple of $2019$ .

Nice usage of pigeonhole principle to show the existence of a solution, without nailing down exactly what it is. For such construction problems, we do not need to find such an $n$ , we just need to prove that it exists.

In this case, if desired, we can find the number directly. Observe that $\frac{X_n} { 2018 } \times 9999 = 10^{4n } - 1$ . (Skipped a step here, see if you can fill in the gap.) Hence, we just need to find when $10^ {4n} - 1 \equiv 0 \pmod{6057}$ . Using fermat's little theorem , since $\phi(6057) = 4032$ , we know that $10^ { 4032 } \equiv 1 \pmod{2019}$ . In particular, $n = \frac{4032}{4} = 1008$ works.

Note: This may not be the smallest $n$ . To get that, we would want to use the order of 10 mod 6057 . It turns out that there is a smaller $n$ that works. Which numbers do we need to test, and why?
Hint: We do not need to test all 1008 numbers. We need to test at most 50 numbers.

@Salvador Júnior

Calvin Lin Staff - 2 years, 11 months ago

Edit: This comment caused me to edit my top level comment, so it might be confusing what is happening here. Figure it out yourself! - Calvin

This is my approach (maybe not the better one):

The order of a number modulo $n$ always divides $\phi (n)$ . The divisors of $1344$ are:

$d(1344)={1, 2, 3, 4,6,7,8,12,14,16,21,24,28,32,42,48,56,64,84,96,112,168,192,224,336,449,672,1344}$ , in a total of 28 divisors.

We now test $10^d$ , being $d$ a divisor of $1344$ . Starting from 1, we find that $224$ works meaning that it is the order of 10 mod 2019 . It means that all numbers in the form $10^{224k}$ leave remainder 1 in the division by 2019. Using the original expression we can find that only when $k$ is a multiple of 3 is when we have $X_n \equiv 0\quad (\text{mod 2019}$ ).

Then, the smallest $X_n$ that is a multiple of 2019 is when $n=3\times 224 \div 4 = 168$

Victor Paes Plinio - 2 years, 11 months ago

Indeed. The "skipped minor step" isn't so minor, and actually isn't true. Let me edit it now.

What we actually have is $X_n \equiv 0 \pmod{2019} \Leftrightarrow \frac{ X_n }{ 2018} \times 9999 \equiv 0 \pmod{2019 \times \gcd(2019,9999)}$ . So, we actually need to work with $\phi (2019 \times 3) = 4032$ .

Calvin Lin Staff - 2 years, 11 months ago

@Calvin Lin – Now I understand. We can't simple divide or multiply both sides of a congruence equation by any number we want like an algebraic equation.

In fact, if $ax \equiv ay \quad (\text{mod n})$ , and $\text{gcd}(a, n) = b$ , the following relation will be true:

$\frac{ax}{a} \equiv \frac{ay}{a} \quad \text{(mod \$\frac{n}{b}\$)}$

The only case we can simply divide or multiply both sides by some number $c$ is when $\text{gcd}(c, n) = 1$

We need find $n$ such that $X_n \equiv 0 \quad (\text{mod 2019})$ .

$X_n=\frac{(10^{4n } - 1)2018}{9999}$

$\frac{(10^{4n } - 1)2018}{9999} \equiv 0 \quad (\text{mod 2019})$

We can divide both sides by 2018 and still being in modulo 2019 $\text{gcd}(2019,2018)=1$ :

$\frac{10^{4n } - 1}{9999} \equiv 0 \quad (\text{mod 2019})$

If we multiply both sides of the equation by $9999$ we need to multiply the modulo that we are working by $\text{gcd}(2019, 9999) =3$ and we will finally get

$10^{4n } - 1 \equiv 0 \quad (\text{mod 6057})$

$\phi(6057)=4032$

From here we can work with the divisors of $4032$ to find the order of 10 modulo 6057 and do the same as I did above.

Victor Paes Plinio - 2 years, 11 months ago

@Victor Paes Plinio – Indeed. That would explain why the initial approach of finding the order of 10 mod 2019 gave an answer that didn't work numerically.

The "multiply/divide by any number without checking gcd" is a very common mistake in such congruences. What is a simple way of understanding that

$x \equiv y \pmod(n) \Leftrightarrow ax \equiv ay \pmod{ n \times \gcd(a,n) } ?$

Calvin Lin Staff - 2 years, 11 months ago

I don't really understand how we know there are exactly $4i$ $0$ 's

in this line of the proof. Could anyone help make it clear for me?

Ahmed Soulmani - 2 years, 10 months ago

Oh I just realized $2018$ is a $4$ -digit number, and that there are $i$ of them! Subtracting that from ${ X }_{ j }$ leaves us with $4i$ $0$ 's.

Very elegant proof I must say!

Ahmed Soulmani - 2 years, 10 months ago

2018 2018 2 0 1 8 as a multiple of 2019 2019 2 0 1 9

1 solution

0 pending reports

$2018$ as a multiple of $2019$