Answer to Question #336062 in Discrete Mathematics for khushi

Question

If 20 candidates appear in a competitive exam. Then show that there exist at least 2 students among them whose roll number differ by a multiple of 19.

Answer 1

Let us consider reminders of roll numbers mod 19.

We have 20 numbers, but there are just 19 possible remainders. By the Pigeonhole Principle, there must be two roll numbers that have the same remainder mod 19. Their difference will be congruent to 0 mod 19 and thus is divisible by 19.