2

enter image description here

I don't quite understand why $s_j$ $-$ $s_j$ is divisible by $2003$ means that there is an element in this sequence that is divisible by $2003$. Aren't they trying to prove for one single element? Not for a difference of the sequence's two elements?

  • Why are you asking about divisibility by $6$? In any case, the text carefully explains why $2003,|, s_j-s_i\implies 2003,|,s_{j-i}$. – lulu Oct 14 '19 at 16:02
  • @lulu so sorry, divisible by 2003. Doesn't 2003 | $s_j$ $-$ $s_i$ mean that 2003 is divisible by $s_j$ $-$ $s_i$ . And i'm asking about the opposite. They show that $s_j$ $-$ $s_i$ is divisible by 2003 but how does this imply that an element of S is divisible by 2003? –  Oct 14 '19 at 16:07
  • No. $a,|,b$ means that "$a$ divides $b$". For instance $4,|,12$. – lulu Oct 14 '19 at 16:08
  • That a difference being divisible by 2003 implies an element being divisible is exactly what has been shown in part (i). – celtschk Oct 14 '19 at 16:08
  • Did you read part i)? Part one says that if there are any $s_i, s_j$ so that $s_i - s_j$ is divisible by $2003$ then there is an element is $S$ that is divisible by $2003$. .... So what part of part i) did you not understand. – fleablood Oct 14 '19 at 16:13
  • Okay, I think I understood it. Although maybe I just found it hard to understand in the first place why would there be an integer which is the difference of two elements divisible by 2003. How do we know that there is actually any integers that are divisible by 2003? –  Oct 14 '19 at 16:18
  • 1
    " I just found it hard to understand in the first place why would there be an integer which is the difference of two elements divisible by 2003" And that's part ii)!!!! – fleablood Oct 14 '19 at 16:24
  • Okay, maybe it would be easier if the book had reversed the order. part ii) by pigeon whole there are two $s_j$ and $s_i$ so that they have the same remainder. So $2003$ divide ($s_j - s_i)$. That was part ii). Now $s_j-s_i = s_{j-i}10^i$ and as $2003$ divides $s_j-s_i=s_{j-i}10^i$ and $2003$ doesn't divide $10^i$ then $2003$ divides $s_{j-i}$. That's part ii). So.... we proved our result. – fleablood Oct 14 '19 at 16:28
  • @ThePoorJew , could you tell me the source of this problem? This seems like a really nice problem with an equally elegant solution. I hope that the source of this problem will have other great problems as well. – Anurag Saha Oct 14 '19 at 16:34
  • @AnuragSaha https://www.cse.iitk.ac.in/users/hk/cs201/2017/exams/quiz2.pdf –  Oct 14 '19 at 16:35
  • @fleablood I now see. It was a confusing order for me indeed. –  Oct 14 '19 at 16:36
  • FWIW I think that solution is incorrect. part i) is correct in that if there are two element so that $2003|s_j-s_i$ then $2003|s_{j-i}$ but part ii) doesn't prove that there are two such elements in the first place (there aren't) but is a statement that either there is a $s_k$ so that $2003|s_k$ BUT IF THERE IS NOT *THEN* there are $s_j$ and $s_i$ so that $2003|s_j-s_i$ (and therefore $2003|s_{j-i}$.) – fleablood Oct 14 '19 at 16:54

1 Answers1

0

Because .... part i)

Just read part ii) first and then part i).

PART II

A statement of contradiction. If $2003$ doesn't divide any $s_k$ then there are only $2002$ possible remainders for $s_k$ divided by $2003$. By Pigeon hole two have the same remainder. Let $s_j$ be the larger and $s_i$ be the smaller. So $s_j - s_i$ has remainder $0$ and $2003$ divides $s_j - s_i$.

PART II

$s_j - s_i = 10^i*s_{j-i}$ and $2003$ is prime and does not divide $10^i$. So if $2003|s_j - s_i$ then $2003|s_{j-i}$.

.....

So proof by contradiction:

If $2003$ doesn't divide any $s_k$ then by PART I, we have that there are $s_j$ and $s_i$ so that $2003|s_j - s_i$ and by PART II we have $2003|s_{j-i}$.

That's a contradiction so $2003$ divides some $s_k$.

fleablood
  • 124,253