Is there a number in the form $n$ times 2 0 1 8 2 0 1 8 2 0 1 8 2 0 1 8 . . . 2 0 1 8 with 2 0 1 8 repeating n times that is a multiple of 2 0 1 9 ?
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.
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 2 0 1 8 X n × 9 9 9 9 = 1 0 4 n − 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 6 0 5 7 ) . Using fermat's little theorem , since ϕ ( 6 0 5 7 ) = 4 0 3 2 , we know that 1 0 4 0 3 2 ≡ 1 ( m o d 2 0 1 9 ) . In particular, n = 4 4 0 3 2 = 1 0 0 8 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
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 always divides ϕ ( n ) . The divisors of 1 3 4 4 are:
d ( 1 3 4 4 ) = 1 , 2 , 3 , 4 , 6 , 7 , 8 , 1 2 , 1 4 , 1 6 , 2 1 , 2 4 , 2 8 , 3 2 , 4 2 , 4 8 , 5 6 , 6 4 , 8 4 , 9 6 , 1 1 2 , 1 6 8 , 1 9 2 , 2 2 4 , 3 3 6 , 4 4 9 , 6 7 2 , 1 3 4 4 , in a total of 28 divisors.
We now test 1 0 d , being d a divisor of 1 3 4 4 . Starting from 1, we find that 2 2 4 works meaning that it is the order of 10 mod 2019 . It means that all numbers in the form 1 0 2 2 4 k 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 ≡ 0 ( mod 2019 ).
Then, the smallest X n that is a multiple of 2019 is when n = 3 × 2 2 4 ÷ 4 = 1 6 8
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 2 0 1 9 ) ⇔ 2 0 1 8 X n × 9 9 9 9 ≡ 0 ( m o d 2 0 1 9 × g cd ( 2 0 1 9 , 9 9 9 9 ) ) . So, we actually need to work with ϕ ( 2 0 1 9 × 3 ) = 4 0 3 2 .
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 ) , and 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 gcd ( c , n ) = 1
We need find n such that X n ≡ 0 ( mod 2019 ) .
X n = 9 9 9 9 ( 1 0 4 n − 1 ) 2 0 1 8
9 9 9 9 ( 1 0 4 n − 1 ) 2 0 1 8 ≡ 0 ( mod 2019 )
We can divide both sides by 2018 and still being in modulo 2019 gcd ( 2 0 1 9 , 2 0 1 8 ) = 1 :
9 9 9 9 1 0 4 n − 1 ≡ 0 ( mod 2019 )
If we multiply both sides of the equation by 9 9 9 9 we need to multiply the modulo that we are working by gcd ( 2 0 1 9 , 9 9 9 9 ) = 3 and we will finally get
1 0 4 n − 1 ≡ 0 ( mod 6057 )
ϕ ( 6 0 5 7 ) = 4 0 3 2
From here we can work with the divisors of 4 0 3 2 to find the order of 10 modulo 6057 and do the same as I did above.
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 × g cd ( a , n ) ) ?
I don't really understand how we know there are exactly 4 i 0 's
X j − X i = $j$ times 2 0 1 8 . . . 2 0 1 8 − $i$ times 2 0 1 8 . . . 2 0 1 8 = $j-i$ times 2 0 1 8 . . . 2 0 1 8 $4i$ times 0 0 0 0 0 0 . . 0 0 0 0
in this line of the proof. Could anyone help make it clear for me?
Log in to reply
Oh I just realized 2 0 1 8 is a 4 -digit number, and that there are i of them! Subtracting that from X j leaves us with 4 i 0 's.
Very elegant proof I must say!
Problem Loading...
Note Loading...
Set Loading...
Let X n = $n$ times 2 0 1 8 2 0 1 8 2 0 1 8 2 0 1 8 . . . 2 0 1 8 . Observe the following list of X n numbers:
X 1 = 1 times 2 0 1 8
X 2 = 2 times 2 0 1 8 2 0 1 8 2 0 1 8 2 0 1 8 . . . 2 0 1 8
X 3 = 3 times 2 0 1 8 2 0 1 8 2 0 1 8 2 0 1 8 . . . 2 0 1 8
. . .
X 2 0 2 0 = 2020 times 2 0 1 8 2 0 1 8 2 0 1 8 2 0 1 8 . . . 2 0 1 8
. . .
In the division by 2 0 1 9 there are 2 0 1 9 possible remainders. In the list above we have 2 0 2 0 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 2 0 1 9 . It means that the difference between these two numbers is a multiple of 2 0 1 9 :
X j − X i = $j$ times 2 0 1 8 . . . 2 0 1 8 − $i$ times 2 0 1 8 . . . 2 0 1 8 = $j-i$ times 2 0 1 8 . . . 2 0 1 8 $4i$ times 0 0 0 0 0 0 . . 0 0 0 0
X n = $j-i$ times 2 0 1 8 . . . 2 0 1 8 $4i$ times 0 0 0 0 0 0 . . 0 0 0 0 = $j-i$ times 2 0 1 8 . . . 2 0 1 8 × 1 0 4 i = X j − i × 1 0 4 i
The boxed number must be a multiple of 2 0 1 9 . The part 1 0 4 i isn't a multiple of 2 0 1 9 , so the part X j − i = $j-i$ times 2 0 1 8 . . . 2 0 1 8 must be a multiple of 2 0 1 9 .
Hence, the answer for this question is YES , there is a number in the form $n$ times 2 0 1 8 2 0 1 8 2 0 1 8 2 0 1 8 . . . 2 0 1 8 that is a multiple of 2 0 1 9 .