2018 2018 as a multiple of 2019 2019

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

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

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

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

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

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

. . . ...

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

. . . ...

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

X j X i = 2018...2018 $j$ times 2018...2018 $i$ times = 2018...2018 $j-i$ times 000000..0000 $4i$ times 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 = 2018...2018 $j-i$ times 000000..0000 $4i$ times = 2018...2018 $j-i$ times × 10 4 i = X j i × 10 4 i 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 2019 . The part 10 4 i {10}^{4i} isn't a multiple of 2019 2019 , so the part X j i = 2018...2018 $j-i$ times X_{j-i}=\underbrace{2018...2018}_{\text{\$j-i\$ times}} must be a multiple of 2019 2019 .

Hence, the answer for this question is YES , there is a number in the form 2018201820182018...2018 $n$ times \underbrace{2018201820182018...2018}_{\text{\$n\$ times}} that is a multiple of 2019 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 n , we just need to prove that it exists.

In this case, if desired, we can find the number directly. Observe that X n 2018 × 9999 = 1 0 4 n 1 \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 1 0 4 n 1 0 ( m o d 6057 ) 10^ {4n} - 1 \equiv 0 \pmod{6057} . Using fermat's little theorem , since ϕ ( 6057 ) = 4032 \phi(6057) = 4032 , we know that 1 0 4032 1 ( m o d 2019 ) 10^ { 4032 } \equiv 1 \pmod{2019} . In particular, n = 4032 4 = 1008 n = \frac{4032}{4} = 1008 works.

Note: This may not be the smallest n n . To get that, we would want to use the order of 10 mod 6057 . It turns out that there is a smaller n 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

Log in to reply

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 n always divides ϕ ( n ) \phi (n) . The divisors of 1344 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 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 1 0 d 10^d , being d d a divisor of 1344 1344 . Starting from 1, we find that 224 224 works meaning that it is the order of 10 mod 2019 . It means that all numbers in the form 1 0 224 k 10^{224k} leave remainder 1 in the division by 2019. Using the original expression we can find that only when k k is a multiple of 3 is when we have X n 0 ( mod 2019 X_n \equiv 0\quad (\text{mod 2019} ).

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

Victor Paes Plinio - 2 years, 11 months ago

Log in to reply

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 0 ( m o d 2019 ) X n 2018 × 9999 0 ( m o d 2019 × gcd ( 2019 , 9999 ) ) 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 ϕ ( 2019 × 3 ) = 4032 \phi (2019 \times 3) = 4032 .

Calvin Lin Staff - 2 years, 11 months ago

Log in to reply

@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 a x a y ( mod n ) ax \equiv ay \quad (\text{mod n}) , and gcd ( a , n ) = b \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 c is when gcd ( c , n ) = 1 \text{gcd}(c, n) = 1

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

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

( 1 0 4 n 1 ) 2018 9999 0 ( mod 2019 ) \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 gcd ( 2019 , 2018 ) = 1 \text{gcd}(2019,2018)=1 :

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

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

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

ϕ ( 6057 ) = 4032 \phi(6057)=4032

From here we can work with the divisors of 4032 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

Log in to reply

@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 y ( m o d ( ) n ) a x a y ( m o d n × gcd ( a , n ) ) ? 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 4 i 4i 0 0 's

X j X i = 2018...2018 $j$ times 2018...2018 $i$ times = 2018...2018 $j-i$ times 000000..0000 $4i$ times 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}}

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

Ahmed Soulmani - 2 years, 10 months ago

Log in to reply

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

Very elegant proof I must say!

Ahmed Soulmani - 2 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...