I Did See You Before!

Consider the following arithmetic sequence { a n } n = 1 \{a_n\}_{n=1}^\infty of positive integers:

10000 , 10103 , 10206 , 10000, 10103, 10206, \cdots{ } \cdots{ } \cdots{ }

Find the smallest positive integer m m , for which there exists at least one positive integer n n (with n < m n<m ) such that a m a n ( m o d 2017 ) . a_m \equiv a_n (\mod{ }2017). .

Note :


The answer is 2018.

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

Brian Moehring
Jun 28, 2018

We can directly check a n = 10000 + 103 ( n 1 ) a_n = 10000 + 103(n-1)

Then a m a n ( m o d 2017 ) 10000 + 103 ( m 1 ) 10000 + 103 ( n 1 ) ( m o d 2017 ) 103 m 103 n ( m o d 2017 ) a_m \equiv a_n \pmod{2017} \\ 10000 + 103(m-1) \equiv 10000 + 103(n-1) \pmod{2017} \\ 103m \equiv 103n \pmod{2017}

Since 2017 2017 is prime and 103 ≢ 0 ( m o d 2017 ) 103\not\equiv 0 \pmod{2017} (or more generally, since gcd ( 103 , 2017 ) = 1 \gcd(103,2017) = 1 ), we can cancel it from both sides to give m n ( m o d 2017 ) , m \equiv n \pmod{2017}, so there exists some integer k k such that m = n + 2017 k m = n + 2017k

Since m > n m > n , k k is positive, so m m is minimized when n = k = 1 n=k=1 , giving m = 1 + 2017 = 2018 m = 1 + 2017 = \boxed{2018}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...