6.9 Number Theory and Combinatorics 115If there is a number among thesennumbers that is divisible byn, then we
have found what we want. If there is none, then let us divide all the numbers
b 1 ,b 2 ,...,bnbynwith residue. Write down these residues. What are the
numbers we were getting? It could be 1, 2 ,...,orn−1. But we have a total
ofnnumbers! So by the pigeonhole principle, there will be two numbers
amongb 1 ,b 2 ,...,bnthat give the same residue when we divide them byn.
Say these two numbers arebiandbj(i<j). Then their differencebj−bi
is divisible byn. But
bj−bi=ai+1+ai+2+···+aj.So we have found a special subset of the numbersa 1 ,a 2 ,...,an, namely
ai+1,ai+2,...,aj, whose sum is divisible byn. And this is what we wanted
to prove.
6.9.1We are givennnumbers from the set{ 1 , 2 ,..., 2 n− 1 }. Prove that we
can always find two numbers among thesennumbers that are relatively prime
to each other.
As a very important application of inclusion–exclusion, let’s answer the
following question about numbers:How many numbers are there up to 1200
that are relatively prime to 1200?
Since we know the prime factorization of 1200,namely, 1200 = 2^4 · 3 · 52 ,
we know that the numbers divisible by any of 2, 3, or 5 are precisely those
that have a common divisor with 1200. So we are interested in counting
the positive integers smaller than 1200 and not divisible by 2, 3, or 5.
One can easily compute that up to 1200, there are
1200
2
numbers divisible by 2(every second number is even),
1200
3numbers divisible by 3,1200
5numbers divisible by 5.Those numbers divisible by both 2 and 3 are just those that are divisible
by 6. Therefore up to 1200 there are
1200
6numbers divisible by 2 and 3,and similarly, there are
1200
10
numbers divisible by 2 and 5,1200
15numbers divisible by 3 and 5.