The 2 million dollars problem

The 2 million dollars math problem

Do you think that someone would pay $2 000 000$ US dollars for the solution of a math problem? Yes, it happened in the history of mathematics that an award of this amount was offered for the solution of the following, apparently simple problem.

Prove that there are no positive integers $x,y,z,n$ with $n\geq 3$ such that

$x^n+y^n=z^n.$

Obviously, solutions for $n=1$ exist: in fact, infinitely many positive integers $x,y,z$ satisfy the diophantine equation $x+y=z$ . For $n=2$ we have an interesting situation: the equation $x^2+y^2=z^2$ is well-known from geometry. Indeed, if we write it with the letters $a^2+b^2=c^2$ then the famous Pythagorean theorem comes to our mind: this is the relation between the legs and the hypotenuse of a right triangle. Of course, this property holds for any right triangle, not just for those where the side lengths are integer numbers. Nevertheless, the Pythagorean equation for integers is an interesting diophantine equation. We call the triple $x,y,z$ of positive integers a Pythagorean triple if it satisfies $x^2+y^2=z^2$ .

pythagorean-triple-mymath4u — Pythagorean triple

Well-known Pythagorean triples are $3,4,5$ and $5,12,13$ . Obviously, we can obtain a new Pythagorean triple from an existing one if we multiply the three numbers with the same integer greater than $1$ . In this way we can create infinitely many Pythagorean triples, although they are not „essentially” different. But, for instance, $5,12,13$ does not arise in this way from $3,4,5$ , hence these two triples are „essentially” different. We call a Pythagorean triple primitive if the three numbers are coprime: their greatest common divisor is $1$ . So, two primitive Pythagorean triples are „essentially” different, hence if we want to describe all solutions of the Pythagorean diophantine equation, then we should focus on primitive triplets.

It was Euclid, who found a method to generate primitive Pythagorean triples by a simple method. He observed that if we take arbitrary integers $m>n>0$ , then $x=m^2-n^2$ , $y=2 m n$ and $z=m^2+n^2$ forms a Pythagorean triple. This is easy to check. Moreover, this triple is primitive if and only if $m,n$ are coprime and not both odd. Clearly, if both are odd, then $x,y,z$ are even, hence they cannot be primitive. For instance, choosing $m=2, n=1$ we get the triple $3,4,5$ , and if $m=3, n=2$ then we obtain $5,12,13$ . Now we have a very nice way to produce as many primitiv Pythagorean triples as we wish – and the reasonable question arises: can we obtain all primitive Pythagorean triples in this way? We can formulate this problem in a more „mathematical” way: easy computation shows that for a triple $x,y,z$ to be a primitive Pythagorean triple it is sufficient to have the above form with some $m>n>0$ , but what about the necessity of this condition? In other words: is Euclid’s above condition for $x,y,z$ is a necessary and sufficient condition to be a primitive Pythagorean triple? The answer is affirmative: Euclid’s smart algorithm produces all possible primitive Pythagorean triples with an appropriate choice of the parameters $m,n$ . The proof of this nice statement is not very difficult: you try to prove it on your own, but if you fail you’ll find the right way in the Problems and Solutions.

So, the cases $n=1,2$ are done and we go to the diophantine equation $x^3+y^3=z^3$ . After spending some time with trial and error we’ll be getting confused. Are there any solutions at all? Around 1637, Pierre Fermat, French mathematician wrote in the margin of a book that the more general equation $x^n + y^n = z^n$ had no solutions in positive integers, if $n$ is an integer greater than $2$ . Although he claimed to have a general proof of his conjecture, Fermat left no details of his proof, and no proof by him has ever been found.

fermat-last-theorem-mymath4u — Pierre de Fermat – Last Theorem

His claim was discovered some 30 years later, after his death. This claim, which came to be known as Fermat’s Last Theorem, stood unsolved in mathematics for the following three and a half centuries. During that time the hunt for solutions, or for a correct proof about non-existence of solutions was one of the most adventurous stories in mathematics. Throughout the 18th and 19th centuries no mathematician could find a counter-example, a set of numbers that fitted Fermat’s equation. Hence, it seemed that the Last Theorem was true, but without a proof nobody could be as sure as Fermat seemed to be. Some of the greatest mathematicians were able to devise specific proofs for individual equations, like $n=3$ and $n=5$ , but nobody was able to match Fermat’s general proof for all equations.

paul-wolfskehl-mymath4u — Paul Wolfskehl

In 1908 Paul Wolfskehl, a German amateur mathematician offered $100000$ German marks (worth $2$ million US dollars today) to whomever succeeded in proving Fermat’s Last Theorem. Within the first year, 621 „proofs” were sent in, most of them from amateur problem-solvers, all of them flawed. After the Second World War computers joined the „hunt”: they proved that for all values of $n$ up to $500$ , then $1000$ , and then $10000$ there were no solutions. In the 1980’s Samuel S. Wagstaff from the University of Illinois raised the limit to $25000$ , and finally it has been proved that for the first four million equations there were no solutions.

In the 1950’s the problem still held a special place in the heart of number theorists, but they viewed it in the same way that chemists thought about alchemy: both were foolish, impossible dreams from a bygone age. But the story hasn’t come to an end yet.

Andrew Wiles was 10 in 1963 when he borrowed a book from his local library in Cambridge, England. He was a pupil with a passion for mathematics. The book, „The Last Problem” recounted the history of Fermat’s Last Theorem. The young Wiles was undaunted: he promised himself that he would devote the rest of his life to addressing the ancient challenge. As a graduate student at Cambridge University, he had concentrated on studying those subjects which were related to Fermat’s problem: elliptic curves. Then as a professor at Princeton University he had continued his research, putting him in an ideal position for attempting a proof.

As he embarked on his proof, he made an extraordinary decision to conduct his research in complete secrecy. He did not want the pressure of public attention, nor did he want to risk others copying his ideas and stealing the prize. The only person who knew about his secret project was his wife – he told her during their honeymoon. For the next seven years he worked in isolation, and his colleagues were oblivious to what he was doing.

Eventually, in 1993, Wiles felt confident that his proof was reaching completion. In his work he used the most advanced mathematics of that time, adding brilliant new ideas to it. There was a special conference at the Isaac Newton Institute in Cambridge, England. Because this was his home town, where he had encountered the Last Theorem as a child, he decided to make a concerted effort to complete the proof in time for that conference. On June 23rd he announced his seven-year calculation to a stunned audience.

His secret research program had apparently been a success, and the mathematical community and the world’s press rejoiced. Fermat’s Last Theorem has been proved.

pierre-de-fermat-mymath4u — Pierre de Fermat

But life was still not easy. After Wiles’ announcement, while the media circus continued the official peer review process began. The rules of the Wolfskehl Prize demanded two years of scrutiny. Over the summer the 200-page proof was examined line by line by a team of referees. Wiles checked and double checked his proof before releasing it to the referees and he was expecting merely grammatical and typographic errors, trivial mistakes. However, gradually it emerged that there was a fundamental and devastating gap in one stage of the argument.

During next year his childhood dream turned into a nightmare. Each attempt to fix the error ended in failure, each attempt to by-pass the error ended in a dead-end. There were calls from the mathematics community to publish the flawed proof, but Wiles steadfastly refused.

richard-taylor-mymath4u — Richard Taylor

After months of failure Wiles did take into his confidence Richard Taylor, a former student of him. By September 1994 they were at the point admitting defeat, ready to release the flawed proof so that others could try and fix it. Still on September 19th they made the vital breakthrough and found the key to the correct proof. Wiles: „It was so indescribably beautiful, it was so simple and so elegant. The first night I went back home and slept on it. I checked through it again the next morning and, and I went down and told my wife, ‘I’ve got it! I think I’ve found it !’. And it was so unexpected that she thought I was talking about a children’s toy or something, and she said, ‘Got what?’ I said, ‘I’ve fixed my proof. I’ve got it!”

And more: ” There’s no other problem that will mean the same to me. This was my childhood passion. There’s nothing to replace that. I had this very rare privilege of being able to pursue in my adult life what had been my childhood dream. I know it’s a rare privilege, but if you can tackle something in adult life that means that much to you, than it’s more rewarding than anything imaginable „.

Yes, it is. Math research is an obsession – in the best sense. You never give it up – you’ll get what you deserve. This is clearly illustrated by the story of Wiles and his fight with Fermat’s Last Theorem. Nevertheless, this world-famous theorem has a „younger brother”, called Fermat’s Little Theorem. It is also about number theory – what else?

More precisely, it is about modular arithmetic and it is a very useful result. It says that if $a$ is any integer then, for each prime number $p$ , the difference $a^p-a$ is divisible by $p$ . In other words, $a^p$ and $a$ belong to the same residue class with respect to $p$ . In terms of congruences we can write $a^p\equiv a\enskip(mod\enskip p)$ . There are several proofs of this statement. Clearly, it is enough to prove the statement for nonnegative values of $a$ hence we can apply induction on $a$ . The statement is obviously true for $a=0$ . We assume that we proved it for $a=k\geq 1$ and we prove it for $a=k+1$ . For this we apply the „freshman’s dream”:

$(a+b)^p\equiv a^p+b^p\enskip(mod\enskip p)$

which holds for any integers $a,b$ if $p$ is a prime number. Indeed, this „dream” holds true in modular arithmetic, since by the Binomial Theorem, we have

$(a+b)^p=a^p+\binom{p}{1} a^{p-1} b+\binom{p}{2} a^{p-2} b^2+\dots+ \binom{p}{p-1} a b^{p-1}+b^p.$

The binomial coefficients have the form $\binom{p}{i}=\frac{p!}{i!\,(p-i)!}$ . For $0<i<p$ neither of the two factors in the denominator has a factor divisible by $p$ , however the numerator has the factor $p$ , hence

$\binom{p}{i}\equiv 0\enskip(mod\enskip p),\enskip\text{and}\enskip (a+b)^p\equiv a^p+b^p\enskip(mod\enskip p).$

Using „freshman’s dream” and our induction hypothesis we have

$(k+1)^p\equiv k^p+1^p\equiv k+1\enskip(mod\enskip p)$

which is the statement for $a=k+1$ .

Obviously, Fermat’s Little Theorem implies that $a^{p-1}\equiv 1 \enskip(mod\enskip p)$ if the prime $p$ does not divide $a$ . Indeed, if $p$ divides $a^p-a=a(a^{p-1}-1)$ , but $p$ does not divide the first factor, then $p$ divides the second factor, since $p$ is a prime. And conversely, if we have this latter „Little Theorem”, then, multiplying both sides by $a$ we get the original form. Don’t forget: the second version holds only if $p$ does not divide $a$ .

To conclude this section let’s see a nice application of Fermat’s Little Theorem. The question is if there is a number in the infinite sequence $2, 22, 222,\dots, 2222,\dots$ divisible by $59$ ? The $n$ -th number in this sequence consists of $n$ digits all equal to $2$ . First we observe that the number consisting of $n$ digits of $2$ is $2\cdot \frac{10^n-1}{9}$ . As $59$ is a prime number Fermat’s Little Theorem says that

$10^{58}\equiv 1\enskip (mod\enskip 59).$

Taking $k$ -th powers we have

$10^{58k}\equiv 1\enskip (mod\enskip 59),$

that is, $59$ divides $10^{58k}-1$ for each positive integer $k$ . Hence $59$ divides $222\dots222$ whenever this number consists of $n=48k$ digits ( $k=1,2,\dots$ ).

digitális matek

The 2 million dollars math problem

Matematika egyetemistáknak, főiskolásoknak.