## And Fermats Last Theorem

The methods of Diophantus May cease to enchant us After a life s pent trying to gear 'em To Fermat's Last Theorem.

An old chestnut, common in puzzle books of the late 19th century (when prices of farm animals were much lower than today), goes like this. A farmer spent \$100 to buy 100 animals of three different kinds. Each cow cost \$10, each pig \$3 and each sheep 50 cents. Assuming that he bought at least one cow, one pig and one sheep, how many of each animal did the farmer buy?

At first glance this looks like a problem in elementary algebra, but the would-be solver quickly discovers that he has written a pair of simultaneous equations with three unknowns, each of which must have a value that is a positive integer. Finding integral solutions for equations is today called Diophantine analysis. In earlier centuries such analysis allowed integral fractions as values, but now it is usually restricted to whole numbers, including zero and negative integers. Of course in problems such as the one I have cited the values must be positive integers. Diophantine problems abound in puzzle literature. The well-known problem of the monkey and the coconuts, and the ancient task of finding right-angle triangles with integral sides, are among the classic instances of Diophantine problems.

The term "Diophantine" derives from Diophantus of Alexandria. He was a prominent Greek mathematician of his time, but to this day no one knows in what century he lived. Most authorities place him in the third century a.d. Nothing is known about him except some meager facts contained in a rhymed problem that appeared in a later collection of Greek puzzles. The verse has been quoted so often and its algebraic solution is so trivial, that I shall not repeat it here. If its facts are correct, we know that Diophantus had a son who died in bis middle years and that Diophantus lived to the age of 84. About half of his major work, Arithmetica, has survived. Because many of its problems call for a solution in whole numbers, the term Diophantine became the name for such analysis. Diophantus made no attempt at a systematic theory, and almost nothing is known about Diophantine analysis by earlier mathematicians.

Today Diophantine analysis is a vast, complex branch of number theory with an enormous literature. There is a complete theory only for linear equations. No general method is known (it may not even exist) for solving equations with powers of 2 or higher. Even the simplest nonlinear Diophantine equation may be fantastically difficult to analyze. It may have no solution, an infinity of solutions or any finite number. Scores of such equations, so simple a child can understand them, have resisted all attempts either to find a solution or to prove none is possible.

The simplest nontrivial Diophantine equation has the linear form ax + by = c, where x and y are two unknowns and a, b and c are given integers. Let us see how such an equation underlies the puzzle in the opening paragraph. Letting x be the number of cows, y the number of pigs and z the number of sheep, we can write two equations:

To get rid of the fraction, multiply the first equation by 2. From this result, 20% + 6y + z = 200, subtract the second equation. This eliminates z, leaving 19x + 5y= 100. How do we find integral values for x and 31? There are many ways, but I shall give only an old algorithm that utilizes continued fractions and that applies to all equations of this form.

Put the term with the smallest coefficient on the left: 5y = 100- 19x. Dividing both sides by 5 gives > = (100- 19x)/5. We next divide 100 and 19x by 5, putting the remainders (if any) over 5 to form a terminal fraction. In this way the equation is transformed to y = 20 - 3x - 4x/5.

It is obvious that iiF at and y are positive integers (as they must be), * must have a posi ti ve value that will make 4xJ5 an integer. Clearly x must be a multiple of 5. The lowest such multiple is 5 itself. This gives y a value of 1 and z (going back to either of the two original equations) a value of 94. We have found a solution: 5 cows, 1 pig* S4 sheep. Are there other solutions? If negative integers are a] Lowed, there are an infinite number, but here we cannot allow negative animals. When x is given a value of 10, or any higher multiple of 5, y becomes negative. The problem therefore has only one solution.

In this easy example the first integral fraction obtained, 4x/5, does not contain a y term. For equations of the same form but with larger coefficients, the procedure just described must often be repeated many times. The terminal fraction is made equal to a new unknown integer, say a, the term with the lowest coefficient is put on the left, and the procedure is repeated to obtain a new terminal fraction. Eventually you are sure to end with a fraction that has only one unknown and is simple enough so that you. can see what values the unknown must have to make the Fraction integral. By working backward through whatever series of equations has been necessary, the original problem is solved.

For an example of an equation similar to the one just analyzed that has no solution, assume that cows cost \$5, pigs \$2 and sheep 50 cents. The two equations are handled exactly as before. The first is doubled to eliminate the fraction and the second is subtracted, producing the Diophantine equation 9x + 3y= 100. Using the procedure of continued fractions, you end with 31 = 33 — 3x — 1/3, which shows that if x is integral, y cannot be. In this case, however, we can tell at once that 9x + 3y= 100 has no solution by applying the following old theorem. If the coefficients of x and y have a common factor that is not a factor of the number on the right, the equation is unsolvable in integers. In this case 9 and 3 have 3 as a common divisor, but 3 is not a factor of 100. It is easy to see why the theorem holds. If the two terms on the left are each a multiple of n, so will their sum be; therefore the term on the right also must be a multiple of ra. An even simpler instance would be 4x + 8^= 101. The left side of the equality obviously must be an even integer, so that it cannot equal the odd number on the right. It is also good to remember that if all three given numbers do have a common factor, the equation can immediately be reduced by dividing all terms by the common divisor.

As an example of a variant of the basic problem that has a finite number (more than one) of positive-integer solutions, consider the case in which cows cost \$4, pigs \$2 and sheep a i third of a dollar. As before, the farmer spends f 100 on 100 animals, buying at least one of each. How many of each does he buy?

Many geometric problems are solved by finding integral solutions for Diophantine equations. In the chapter on triangles flu my Mathematical Circus I gave two classic examples: Finding - integer solutions for a problem involving two crossed-ladders, and for a problem concerning the location of a spot inside an Ijfquilateral triangle. Among the many geometrical Diophantine alems that are still unsolved, one of the most difficult and bifttorious is known as the problem of the "integral brick" or ational cuboid." The "brick" is a rectangular parallelepiped, iere are seven unknowns: The brick's three edges, its three Ce diagonals, and the space diagonal that goes from one cor-through the brick's center to the opposite corner [see Figure H Can a brick exist for which all seven variables have integer lues?

Figure 8

Figure 8

The integral brick, an unsolved Diophantine problem

The problem is equivalent to finding integer solutions for the seven unknowns in the following set of equations:

The problem has not been shown to be impossible, nor has it been solved. John Leech, a British mathematician, has been searching for a solution, and I am indebted to him for the following information. The smallest brick with integral edges and face diagonals (only the space diagonal is nonintegral) has edges of 44, 117 and 240. This was known by Leonhard Euler to be the minimum solution. If all values are integral except a face diagonal, the smallest brick has edges of 104, 153 and 672, a result also known to Euler. (The brick's space diagonal is 697). The third case, where only an edge is nonintegral, has not, as far as Leech knows, been considered before. It too has solutions, but the numbers are, as Leech puts it, "hideous." He suspects that the smallest such brick may be one with edges of 7,800, 18,720, and the irrational square root of 211, 773, 121. Of course the brick's volume is also irrational.

A much easier geometric problem, which I took from a puzzle book by L. H. Longley-Cook, is illustrated in Figure 9. A rectangle (the term includes the square) is drawn on graph paper as shown and its border cells are shaded. In this case the shaded cells do not equal the unshaded cells of the interior rectangle. Is it possible to draw a rectangle of proportions such that the border—one cell wide—contains the same number of cells as there are within the border? If so, the task is to find all such solutions. The Diophantine equation that is involved can be solved easily by a factoring trick, which I shall explain in the answer section.

 s 11 — — — - 3 ■ ■ -r - US H _1 □ ffl I" [33J

A simple Diophantine problem

### A simple Diophantine problem

In ancient times the most famous Diophantine problem, posed by Archimedes, became known as the "cattle problem." It involves eight unknowns, but the integral solutions are so huge (the smallest value contains more than 200,000 digits) that it was not solved until 1965 when a computer managed to do it. The interested reader will find a good discussion of the cattle problem in Eric Temple Bell's The Last Problem, and the final solution, by H. C. Williams and others, in the journal Mathematics of Computation (see bibliography).

The greatest of all Diophantine problems, still far from solved, is the "last theorem" of Pierre de Fermat, the 17th-century French amateur number theorist. (He was a jurist by profession.) Every mathematician knows how Fermat, reading Diophantus' Arithmetiea, added a note in Latín to the eighth problem of the second book, where an integral solution is asked for ¡P+y2 = a2. Fermat wrote that such an equation had no solution in integers for powers greater than 2. (When the power is 2, the solution is called a "Pythagorean triple" and there are endless numbers of solutions.) In brief, Fermat asserted that xn+y" = an has no solution in integers if n is a positive integer greater than 2. "I have discovered a truly marvelous demonstration," Fermat concluded his note, "which this ¡margin is too narrow to contain."

To this day no one knows if Fermat really had such a proof. Decause the greatest mathematicians since Fermat have failed to find a proof, the consensus is that Fermat was mistaken. Lin-< raring doubts arise from the fact that Fermat always did have £ proof whenever he said he did. For example, consider the Diophantine equation yi=x<¿ + 2. It is easy to find by trial and Ifrror that it has the solutions 33 = 52 + 2 and 33 = -52 + 2. To prove, however, that there are no other integral solutions, Bell writes in Men of Mathematics, "requires more innate intellectual capacity . . . than it does to grasp the theory of relativity." Fer-ipat said he had such a proof although he did not publish it. "This time he was not guessing," Bell continues. "The problem is hard; he asserted that he had a proof; a proof was later found." Fermat did publish a relatively elementary proof that X4 +y = a4 has no solution, and later mathematicians proved the impossibility of the more difficult x3 +>3 = a3. The cases of n = 5 and n = 7 were settled early in the 19th century.

It can be shown that Fermat's last theorem is true if it holds for all prime exponents greater than 2. By 1978 the theorem had been proved for all exponents less than 125,000, so if there is a counterexample it will involve numbers with more than a million digits. Proving the theorem continues to be the deepest unsolved problem in Diophantine theory. Some mathematicians believe it may be true but unprovable, now that Kurt Gódel has shown, in his famous undecidability proof, that arithmetic contains theorems that cannot be established inside the deductive system of arithmetic. (If Fermat's last theorem is Godelian-undecidable, it would have to be true, because if it were false, it would be decidable by a single counterexample.)

I earnestly ask readers not to send me proofs. I am not competent to evaluate them. Ferdinand Lindemann, the first to prove (in 1882) that pi is transcendent, once published a long proof of Fermat's last theorem that turned out to have its fatal mistake right at the beginning. Dozens of other fallacious proofs have been published by leading mathematicians. When David Hilbert was asked why he never tackled the problem, his reply was: "Before beginning I should put in three years of intensive study, and I haven't that much time to squander on a probable failure."

The mathematics departments of many large universities return all proofs of Fermat's last theorem with a form letter stating that the paper will be evaluated only after an advance payment of a specified fee. Edmund Landau, a German mathematician, used a form letter that read: "Dear Sir/Madam: Your proof of Fermat's last theorem has been received. The first mistake is on page _, line_." Landau would then assign the filling in of the blanks to a graduate student.

Donald E. Knuth whimsically asks for a proof of Fermat's last theorem as the last exercise at the end of his preface to the first volume of his series The Art of Computer Programming (1968). His answer states that someone who read a preliminary draft of the book reported that he had a truly remarkable proof but that the margin of the page was too small to contain it.

Euler failed to prove Fermat's last theorem, but he made a more general conjecture that, if it is true, would include the truth of Fermat's last theorem as a special case. Euler suggested that no nth power greater than 2 can be the integral sum of fewer than n nth powers. As we have seen, it has long been known that the conjecture holds when n is 3, for this is merely Fermat's last theorem with powers of 3. It is not yet known whether or not x4+y4 + z4 = a4 has a solution.

In 1966, about two centuries after Euler made his guess, a counterexample was published. Leon J. Lander and Thomas R. Parkin, with the help of a computer program, showed that Euler's conjecture fails for n = 5. The counterexample with the lowest coefficients is:

This result suggests that if there are intelligent creatures living somewhere in a space of five dimensions, their puzzle books surely contain the following problem. What is the smallest hypercube of five dimensions that can be built with unit hy-percubes such that the same number of unit hypercubes will form four smaller hypercubes, with no unit hypercubes left over? The answer is a cube of 144x144x144x144x144 units.

0 0