Page 127 - Discrete Mathematics and Its Applications

106 1 / The Foundations: Logic and Proofs

FIGURE 7 Coloring the Squares of the Standard Checkerboard
with Three Colors.

squares. This contradicts the fact that this board contains 20 blue squares, 21 black squares, and
22 white squares. Therefore we cannot tile this board using straight triominoes. ▲

The Role of Open Problems

Many advances in mathematics have been made by people trying to solve famous unsolved
problems. In the past 20 years, many unsolved problems have finally been resolved, such as the
proof of a conjecture in number theory made more than 300 years ago. This conjecture asserts
the truth of the statement known as Fermat’s last theorem.

THEOREM 1 FERMAT’S LAST THEOREM The equation
n
n
x + y = z n
has no solutions in integers x, y, and z with xyz = 0 whenever n is an integer with n> 2.

2
2
2
Remark: The equation x + y = z has infinitely many solutions in integers x, y, and z; these
solutions are called Pythagorean triples and correspond to the lengths of the sides of right
triangles with integer lengths. See Exercise 32.
This problem has a fascinating history. In the seventeenth century, Fermat jotted in the
margin of his copy of the works of Diophantus that he had a “wondrous proof” that there are no
n
n
n
integer solutions of x + y = z when n is an integer greater than 2 with xyz = 0. However,
he never published a proof (Fermat published almost nothing), and no proof could be found in
the papers he left when he died. Mathematicians looked for a proof for three centuries without
success, although many people were convinced that a relatively simple proof could be found.
(Proofs of special cases were found, such as the proof of the case when n = 3 by Euler and the
proof of the n = 4 case by Fermat himself.) Over the years, several established mathematicians
thought that they had proved this theorem. In the nineteenth century, one of these failed attempts
led to the development of the part of number theory called algebraic number theory. A correct