2 1 Methods of Proof
We continue our illustration of the method of argument by contradiction with an
example of Euler.
Example.Prove that there is no polynomial
P(x)=anxn+an− 1 xn−^1 +···+a 0with integer coefficients and of degree at least 1 with the property thatP( 0 ), P ( 1 ), P ( 2 ),
...are all prime numbers.
Solution.Assume the contrary and letP( 0 )=p,pprime. Thena 0 =pandP(kp)is
divisible bypfor allk≥1. Because we assumed that all these numbers are prime, it
follows thatP(kp)=pfork≥1. Therefore,P(x)takes the same value infinitely many
times, a contradiction. Hence the conclusion.
The last example comes from I. Tomescu’s bookProblems in Combinatorics(Wiley,
1985).
Example.LetF ={E 1 ,E 2 ,...,Es}be a family of subsets withrelements of some
setX. Show that if the intersection of anyr+1 (not necessarily distinct) sets inFis
nonempty, then the intersection of all sets inFin nonempty.
Solution.Again we assume the contrary, namely that the intersection of all sets inFis
empty. Consider the setE 1 ={x 1 ,x 2 ,...,xr}. Because none of thexi,i= 1 , 2 ,...,r,
lies in the intersection of all theEj’s (this intersection being empty), it follows that for
eachiwe can find someEjisuch thatxi∈/Eji. Then
E 1 ∩Ei 1 ∩Ei 2 ∩···∩Eir=∅,since, at the same time, this intersection is included inE 1 and does not contain any
element ofE 1. But this contradicts the hypothesis. It follows that our initial assumption
was false, and hence the sets from the familyFhave a nonempty intersection.
The following problems help you practice this method, which will be used often in
the book.
1.Prove that√
2 +
√
3 +
√
5 is an irrational number.
2.Show that no set of nine consecutive integers can be partitioned into two sets with
the product of the elements of the first set equal to the product of the elements of
the second set.
3.Find the least positive integernsuch that any set ofnpairwise relatively prime
integers greater than 1 and less than 2005 contains at least one prime number.