Question

Pigeonhole principle: Prove that, for any n+1 integers a1,a2,....,a(n+1), there exist two of the integers ai and aj with i not equal to j, such that ai- aj is divisible by n

Answer 1

can you use congruence classes?

Answer 2

any way that can solve this problem would work!

Answer 3

if there are n + 1 numbers, consider Z_n the congruence classes mod n

Answer 4

that is the set {0,1,2,...,n-1} those are your pigeon holes, you have n + 1 pigeons

Answer 5

how that's matter with

Answer 6

ai-aj

Answer 7

ok lets spell it out a little more
but to answer your question, one of those n boxes must have two numbers ai, aj which means that they have the same remainder when divided by n, which is the same thing as saying n divides ai - aj

Answer 8

if the congruence classes is a bit abstract and needs to be fleshed out, a more prosaic way of proof is to consider the remainders of you n + 1 elements when divided by n
there can be at most n such remainders
this should be clear, like if you take the remainder when dividing by 10 there are only ten possibilities

Answer 9

those are your pigeonholes, the n remainders in which you have to put n + 1 pigeons (numbers)
the principle says at least one hole contains at least two pigeons, i.e. two numbers must have the same remainder when dividing by n

Answer 10

"they have the same remainder when divided by n," this really make sense!

Answer 11

then it is clear (right?) that if two numbers have the same remainder when dividing by n, then divides there difference

Answer 12

oops i meant "then n divides their difference"

Answer 13

yes. Thanks for your explanation! really really helpful!

Answer 14

yw