Let n E N and suppose that a1 a2 am are integers where mn pr

Let n E N and suppose that a1, a2, ........am are integers, where m>n. prove that there are distinct integers i and j such that ai and aj are congruent modulo n.

Solution

Given that a1, a2... am are integers. and m>n.

Let m-n = k where k is definitely >0

Let al be one integer in the group ai\'s such that l >n.

Then when al divided by n leaves a remainder either 0 or any number less than n.

Thus al is congruent to r mod n where r is the remainder.

Consider l-n say t

As l >n, at is definitely in the set ai\'s

t will give the same remainder as l as t = l-n

Hence al is congruent to at

Thus proved