Lesson 5

Problem. Consider the following problem.

Prove that there exists a positive integer consisting only of zeros and ones that is divisible by 19.

Is the proof given below correct?

Consider nineteen numbers: \[1, 11, 111, \dotsc, \underbrace{111\dotsb111}_{\text{\(19\) digits}}.\] If one of them is divisible by \(19\), then this number suits us. Otherwise, all these numbers are not divisible by \(19\), that is, they give non-zero remainders when divided by \(19\). Since there are nineteen numbers, and only eighteen non-zero remainders, there will be two numbers giving the same remainder: \[\underbrace{111\dotsb111}_{\text{\(n\) digits}}\bmod 19 = \underbrace{111\dotsb111}_{\text{\(m\) digits}}\bmod 19\] for \(n<m\) (the operation \(\pmod{19}\) denotes the remainder when divided by \(19\)). It remains to note that the difference of these numbers is divisible by \(19\) (since the remainders of the two numbers coincide) and has the form \[\underbrace{111\dotsb111}_{\text{\(m-n\) ones}}\underbrace{000\dotsb000}_{\text{\(n\) zeros}}.\]