be compared and it can be decided that one is "bigger"
or one is "smaller" or they are both equal? (Using the
norm function Ix + iyl = J X^2 + y^2 is "cheating," for
this converts each complex number into a real num
ber and hence eludes the question of whether any two
complex numbers can be compared.)
2.3.17 Prove that if a is rational and b is irrational,
then a + b is irrational.
2.3.18 True or false and why: If a and b are irrational,
then ab is irrational.
2.3.19 Prove the statements made in the discussion of
congruence notation on page 44.
2.3.20 Prove the following generalization of Exam
ple 2.3.4 on page 44:
Let m be a positive integer and let S de
note the set of positive integers less than
m that are relatively prime to m, i.e.,
share no common factor with m other
than J. Then for each xES, there is a
unique y E m such that xy =-I (mod m).For example, if m = 12, then S = {1,5, 7, II}. The
"multiplicative inverse" modulo 12 of each element
xES turns out to be x: 5·5 =-I (mod 12),7·7 =-I
(mod 12), etc.
2.3.21 There are infinitely many primes. Of the many
proofs of this important fact, perhaps the oldest was
known to the ancient Greeks and written down by Eu
clid. It is a classic argument by contradiction. We start
by assuming that there are only finitely many primes
PI,P 2 ,P 3 , ... ,PN. Now (the ingenious crux move!)
consider the number Q:= (PIP 2 P 3 ··· PN) + I.
Complete the proof!
2.3.22 (Putnam 1995) Let S be a set of real numbers
that is closed under multiplication (that is, if a and b
are in S, then so is ab). Let T and U be disjoint sub
sets of S whose union is S. Given that the product of
any three (not necessarily distinct) elements of T is in
T and that the product of any three elements of U is
in U, show that at least one of the two subsets T, U is
closed under multiplication.
2.3.23 (Russia 1995) Is it possible to place 1995 dif
ferent natural numbers along a circle so that for any
two of these numbers, the ratio of the greatest to the
least is a prime?
2.3.24 Complete the solution started in Example 1.1.2
on page I.
2.3 METHODS OF ARGUMENT 512.3.25 If you haven't worked on it already, look at
Problem 2.2.13 on page 37. The correct answer is
(n^2 + n + 2)/2. Prove this by induction.
2.3.26 It is easy to prove that the product of any three
consecutive integers is always divisible by 6, for at
least one of the three integers is even, and at least one
is divisible by 3. Done! This is a very easy proof, but
as an exercise, prove the assertion using induction. It
is less fun, but good practice.
2.3.27 Prove that a set with n elements has 2n subsets,
including the empty set and the set itself. For example,
the set {a, b, c} has the eight subsets0 , {a }, {b}, {c}, {a,b}, {a,e}, {b,c}, {a,b,c}.
2.3.28 Prove the formula for the sum of a geometric
series:an-I +an-^2 + ... + 1= --.
(an - I)
a-I
2.3.29 Prove that the absolute value of the sum of sev
eral real or complex numbers is at most equal to the
sum of the absolute values of the numbers. Note: you
will need first to verify the truth of the triangle in
equality, which states that la + bl :S lal + Ibl for any
real or complex numbers a, b.
2.3.30 Prove that the magnitude of the sum of several
vectors in the plane is at most equal to the sum of the
magnitudes of the vectors.
2.3.3 1 Show that 7n - I is divisible by 6, for all posi
tive integers n.
2.3.32 (Germany 1995) Let x be a real number such
that x + x-I is an integer. Prove that � + x-n is an
integer, for all positive integers n.
2.3.33 Prove Bernoulli's Inequality, which states
that if x > - I, x i= 0 and n is a positive integer greater
than I, then
( 1 +xt > I +nx.2.3.34 After studying Problem 2.2.1 1 on page 37, you
may have concluded that f(n) is equal to the number
of ones in the binary (base-2) representation of n. [For
example, f ( 13) = 3, since 13 is 110 I in binary.] Prove
this characterization of f(n) using induction.
2.3.35 (Bay Area Mathematical Olympiad, 2006)
Suppose that n squares of an infinite square grid are
colored grey, and the rest are colored white. At each
step, a new grid of squares is obtained based on the