Remainder Multiples of 1997

Given any 1000 integers, some two of them differ by, or sum to, a multiple of 1997.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

Given any 1000 integers, some two of them differ by, or sum to, a multiple of 1997.

Form the 999 sets of remainders modulo 1997, {0}, {i, 1997 - i}, for i = 1,... ,998. These sets partition all remainders. Hence two of the given integers, say x and y, have remainders which lie in one of these sets. If x and y have the same remainder, then they differ by a multiple of 1997. Otherwise, their remainders sum to 1997 and so x + y is a multiple of 1997.


Related material
Read more...

  • Sum of Integers
  • More than half of the integers from {1, 2, ..., 2n}
  • Consequences of Getting More Than a Half
  • Intersecting Subsets
  • Over-The-Counter Pigeonhole
  • Women in a theatre: Pigeonhole Principle
  • Pigeonhole Among Friends
  • Not Exceeding 24

  • |Contact| |Front page| |Contents| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71493711