Fermat's last theorem is just one of many examples of innocent-looking problems that can long stymie even the most astute mathematicians. It took about 350 years to prove Fermat's scribbled conjecture, for instance.
Now, Preda Mihailescu of the Swiss Federal Institute of Technology in Zurich has proved a theorem that is likely to lead to a solution of Catalan's conjecture, another venerable problem involving relationships among whole numbers. He presents his result in a paper to be published in the Journal of Number Theory.
"This is a very important contribution," says mathematician Andrew Granville of the University of Georgia in Athens. Mihailescu's work probably puts the resolution of Catalan's conjecture into the foreseeable future, he notes.
Named for Belgian mathematician Eugène Charles Catalan, the conjecture concerns powers of whole numbers. For example, the sequence of all squares and cubes of whole numbers begins with the integers 4, 8, 9, 16, 25, 27, and 36. In this sequence, 8 (the cube of 2) and 9 (the square of 3) are not only powers but also consecutive whole numbers.
In 1844, Catalan asserted that, among all powers of whole numbers, the only pair of consecutive numbers that arises is 8 and 9. His conjecture amounts to a search for whole-number solutions to the equation xp – yq = 1, where x, y, p, and q are all greater than 1. The conjecture suggests that there is only one such solution: 32 – 23 = 1.
Catalan was probably not the first to consider this question. Around 1320, Levi ben Gerson (1288–1344) proved that if powers of 2 and 3 are consecutive, they must be 8 and 9 (see Medieval Harmony, January 23, 1999).
Several centuries later, Leonhard Euler (1707–1783) established that if x2 – y3 = ±1, then x = 3 and y = 2. In his conjecture, Catalan generalized previous results to all powers, but he didn't work on the problem himself.
In 1976, taking a significant step toward resolving Catalan's conjecture, Robert Tijdeman of the University of Leiden in the Netherlands showed that, if the conjecture is not true, there is a finite rather than an infinite number of solutions to the equation. In effect, each of the exponents p and q must be less than a certain value, initially shown to be astronomically huge.
Mathematicians then sought to lower this upper limit. Last year, Maurice Mignotte of the Université Louis Pasteur in Strasbourg, France demonstrated that p had to be less than 7.15 x 1011 and q less than 7.78 x 1016. At the same time, computations showed that no consecutive powers other than 8 and 9 occur for values of p and q less than 107.
In the latest advance, Mihailescu proved that, if additional solutions to the equation exist, the exponents p and q are a pair of what are known as double Wieferich primes. These pairs of prime numbers obey the following relationship: p(q – 1) must leave a remainder of 1 when divided by q2, and q(p – 1) must leave a remainder of 1 when divided by p2.
Only six examples have been identified so far: 2 and 1,093; 3 and 1,006,003; 5 and 1,645,333,507; 83 and 4,871; 911 and 318,917; and 2,903 and 18,787. All of these pairs fall below the range identified by Mignotte as relevant to Catalan's conjecture.
"Double Wieferich primes are extremely rare," says Ray Steiner of Bowling Green State University in Ohio. "Mihailescu's paper makes it likely that there are very few pairs that can satisfy Catalan's equations."
"Unfortunately, there is no known way to determine all such pairs in the range given above without searching the entire range," Steiner says. "It can be shown that this requires testing about 1020 pairs."
"This could probably be done with a massive multi-computer search," he adds, "but unless some way could be found to greatly reduce the number of possible pairs, it may be several years before Catalan's conjecture is completely settled."
It's possible that a theoretical approach may yet pinpoint the solution before the computations are completed.
"I do think that it may well require substantial new work on bounds on linear forms in logarithms, but this is great motivation to do that." Granville says. "On the other hand, it may be that existing results plus some cleverness are enough to get Catalan finished off."