Pigeon Hole Principle :Prove that given any set of n + 1 integers, there must be at least one pair among them whose difference is divisible by n

Step-by-step explanation:When you divide an integer number by n, you get a remainder of either 0, 1, 2, ..., n-1 (for example 5 divided by 2 leaves a remainder of 1, or 13 divided by 5 leaves a remainder of 3, or 16 divided by 2 leaves a remainder of 0, and so on).So there are n different remainders we could get when dividing an integer number by n. If we are given n+1 numbers, they each leave a certain remainder when divided by n. Since there are only n possible remainders, and we have n+1 numbers, by the pigeonhole principle we know there must be at least 2 numbers that leave the same remainder when divided by n. Call them numbers a and b, and let's call r the remainder they leave when divided by n. So both a and b are of the form:[tex] a=kn+r[/tex] (for some integer k)[tex] b=ln+r[/tex] (for some integer l)(this is exactly what it means to leave a remainder of r when divided by n)And so their difference is[tex] a-b=kn+r-(ln+r)=kn-ln=(k-l)n[/tex]Which is divisible by n by definition of being divisible (or think of it as a-b being a multiple of n, so it's divisible by n).