Euler, Erdős

Pierre de Fermat (1607-1665) is my outlier of mathematics: not because math was just a hobby for him — he was a lawyer by profession; nor because he nevertheless laid out the groundwork for several areas of the subject: analytic geometry, calculus, number theory; not because he also contributed Fermat's principle to optics — an explanation of the laws of reflection and refraction; not because he claimed to have (but never published) a neat proof for a statement that took everyone else three centuries to prove — Fermat's Last Theorem; but, on the same note, mainly because he claimed to have (but never published) proofs for any of his statements! Ok, that's a slight exaggeration. Let me put it this way: of all the things he claimed about numbers, we know only of one proof from him. And despite this, he was instrumental in the development of modern number theory.

Fermat struggled to find other mathematicians interested in number theory. In fact, number theory was not a thing in Europe until the 18th century. So in an attempt to spark interest in what he saw as beautiful but neglected area of mathematics, Fermat would challenge other European mathematicians with proving remarkable properties of number, which he'd have supposedly proven. Disclaimer: the following sentence and a lot of others are just my opinion and should taken with a grain of salt. Unfortunately for Fermat, mathematics was more of a tool for science at the time; contemporary mathematicians weren't interested in studying problems that had no real world applications — the classic pure vs. applied math divide. Fortunately for future number theorists, a century later, Euler found a collection of some of Fermat's letters which contained these unproven claims and proceded to work on proving many of them; Euler's work managed to do what Fermat's letters had failed to do and, in 18th century, modern number theory was born. Fermat never published anything in his lifetime but after his death, his son published a new edition of Diophantus' Arithmetica which contained margin notes Fermat made in his copy of the book. There were also posthumous publications of his letters some of which found there way to Euler.

Before diving into Fermat's theorems, here is some context. Two week ago, I watched The Man Who Knew Infinity — the biographical movie based on the life of Ramanujan. In it, Hardy was really tough on Ramanujan for not providing proofs for his statements/theorems. Trying to get Ramanujan to appreciate the importance of proofs, Hardy took him to the Cambridge University Library and showed him the display of Newton's Principia; Hardy explained that Ramanujan was capable of reaching Newton's level of recognition but first he had to learn how to write proofs. This scene captures how fundamental proofs are (or seem to be) to mathematics.

Around the same time, I coincidentally read something about there being only one known proof by Fermat. How could this be?? When I took my introduction to number theory as an undergraduate, it felt like everything we did was linked to Fermat. I knew about the time and math developments it took to prove his famous Last Theorem but I assumed the simpler theorems we proved in class had definitely been proven by him. Turns out: he simply never wrote the proofs for all (except one of) his theorems. And did you find it odd that I called them “his theorems” even though we don't have his proofs? Well here's something even more surprising: no one seems to doubt that he actually had all these proofs (with the one exception of course). Fermat is the only mathematician I know of who got a pass on not giving proofs. Even before its proof was published in 1994, Fermat's Last Theorem was still called a theorem.

This was so fascinating that I had to dig deeper into it. I found out that he never published anything, at least in number theory, in his lifetime; everything was published posthumously. The only record of Fermat's work, at least in number theory, is in his personal letters and his margin notes in Arithmetica. Fortunately for me, everything was collected together and translated to French in the volumes of Oeuvres de Fermat. So I started to track:

1. when he stated his theorems and/or their proofs; and
2. who published the first proofs.

The latter was easy to do since it was Euler for most of them and The Euler Archive has all his published works. Without further ado, here are some of Fermat's theorems.

Little Theorem.

(v1) if \( p \) is prime, then \( a^p \equiv a \pmod p, \) for all \( a \)

(v2) if \( p \) is prime, then \( a^{p-1} \equiv 1 \pmod p, \) for all \( a \not \equiv 0 \pmod p \).

Example 1. Let \( a=3 \) and \( p=5 \).

For v1, we get \( 3^5 \equiv 3 \pmod 5 \), that is, the remainder after dividing \( 3^5~(=243) \) by \( 5 \) is \( 3 \).

For v2, we get \( 3^4 \equiv 1 \pmod 5 \), that is, the remainder after dividing \( 3^4~(=81) \) by \( 5 \) is \( 1 \).

You should try some other examples on your own: \( a = 2, p = 7 \) or \( a=14, p=3 \).

I've given two equivalent versions of the theorem but I must say Fermat did not state it like that; in fact, even the notation I used was created by Gauss over 150 years later. The earliest mention of this theorem that I could find was in Letter 44 to Frenicle (18 Oct. 1640). In that letter, Fermat's Little Theorem is stated along these lines:

Theorem 2. Any (fixed) prime number \( p \) divides one of the listed numbers \( a-1 \), \( a^2 -1 \), \( a^3 -1 \), \( a^4-1 \), \( \ldots \) for any positive integer \( a \). If \( p \) divides \( a^n - 1 \) for some \( n \), then \( n \) divides \( p-1 \). If \( a^{n} - 1 \) is the first element in the list divisible by \( p \), then \( p \) will divide \( a^{nk}-1 \) for all positive integers \( k \).

Example 2.

Let \( a=2, p=7 \). \( 7 \) divides \( 2^3 - 1 \) and \( 3 \) divides \( 7-1 \).

Let \( a=3, p=11 \). \( 11 \) divides \( 3^5-1 \) and \( 5 \) divides \( 11-1 \).

What a mouthful! So putting aside the fact my two versions of the theorem use notation not available to Fermat, their contents (mathematical meaning) are different from his and, technically, his is false: if \( a=p \) then \( p \) will never divide \( a^n-1 \) for all positive integers \( n \). So Fermat was implicitly assuming that \( a \) is not a multiple of \( p \). Furthermore, the last two sentences sort of contradict each other. The third sentence implies we can get arbitrarily large \( n \) for which \( p \) divides \( a^n-1 \). That together with the second sentence implies arbitrarily large integers can divide a fixed number \( p-1 \) but this is absurd. So in the second sentence as well, Fermat was assuming that \( a^n-1 \) was the first element divisible by \( p. \) As this is a letter he was writing to a friend, Fermat was sloppy with his stated assumptions because Frenicle would probably still understand what he meant. Once you've fixed these tiny “mistakes” and added the necessary assumptions, the statement is still different from mine. He was basically saying what I said and then more; in math jargon, we say his version is stronger than mine. And what does Fermat say about proving the theorem? That he would have sent a proof were it not too long for the letter. Doesn't that sound familiar?

v2 is the closest to Fermat's statement since I had to make the assumption “\( a \not \equiv 0 \pmod p \)”, i.e., \( a \) is not a multiple of \( p \). But I didn't have to make the other assumptions because my statement says nothing about dividing \( p-1 \). The second and third sentences in Fermat's statement, which never appear when people write Fermat's little theorem, will be important in a moment as I discuss the theorem's two fundamentally different proofs.

Euler first discovered the theorem (v2) in 1732 while working on Fermat numbers (more on this later) unaware that Fermat too had stated it; it was a conjecture at the end of Euler's paper E026. Euler gave a proof (for v1) in his paper E054 (1735); v1 was more natural since his proof relied on induction and the binomial expansion of \( (a+1)^p \). It was a simple proof and most probably the one that you will get in a number theory class. Euler still does not attribute the theorem to Fermat in this second paper. 19 years later, Euler revisited the topic and gave a second proof (for v2 this time) in E262. This proof uses group theoretic ideas that make v2 the natural form of the theorem. Even though groups were yet to be defined, the proof is similar to the standard one given in a modern algebra class. It is finally in this paper that Euler attributes the theorem to Fermat and actually proves Fermat's version of it; the proof is qualitatively better as it gives better intuition of what's going on (Rule of Thumb: anything that uses group theory is always better). Given the way Fermat stated the theorem, Weil (pg. 1147) argues that the second proof is probably what Fermat had in mind and I can't help but agree. It's hard to see why one would come up with such a wordy statement if it weren't dictated by the proof itself. In contrast, Burton (pg. 514) says that the first proof is simple and what Fermat had in mind but how could he prove the second sentence using induction or the binomial theorem? In the end, Euler was able to generalize the further group theoretic ideas when he proved Euler's theorem in E271 (1757).

Note: The letters of Fermat are all in the Oeuvres de Fermat, Tome 2 and if they are written in latin then you can find French translations in Tome 3. I'm using this collection's numbering scheme when I say “Letter 44” or “Obs. 3.” The latter would be referring to the third margin note in Fermat's copy of Arithmetica. The letters are usually dated but the notes aren't; I read somewhere (forgot where) that we can assume they were written sometime in 1630-1640. Also, all of Euler's papers can be found at The Euler Archive where they are catalogued using labels like “E0262.” The archive has English translations for most of his papers referenced in this post.

Now on to the second claim on my list:

Christmas Theorem. Let \( p \) be an odd prime number.

\( p \) is a sum of two (integer) squares if and only if \( p \) is of the form \( 4n+1 \).

Or using modern notation: \( p = x^2 + y^2 \iff p \equiv 1 \pmod 4 \)

Example 3.

\( 5 = 4\cdot 1 + 1 \) is prime number and \( 5 = 1^2 + 2^2 \).

\( 13 = 4\cdot 3 + 1 \) is prime number and \( 13 = 2^2 + 3^2 \).

However, \( 3 = 4\cdot 0 + 3 \) and \( 7 = 4 \cdot 1 + 3 \) are primes which can never be written as a sum of two integer squares.

Honestly, I saw that name mentioned once on Wikipedia and I couldn't stop myself from using it. Fermat stated it on Christmas 1640 in Letter 45 to Mersenne and again as a margin note, Obs. 7. The theorem is an if and only if statement and one half is easy to show using modular arithmetics: if \( p \) is a sum of two squares, then \( p = 4n+1 \). The really hard part is showing the second half: if \( p = 4n+1 \) then there are integers \( x \) and \( y \) such that \( p= x^2 + y^2. \) Where do you even begin with this? Fermat himself admitted that it took him a while to get a proof and gave us a clue on how he did it in Letter 101 to Carcavi (Aug. 1659). This is what he wrote:

Proof outline: Suppose \( p_1 \equiv 1 \pmod 4 \) were not a sum of two squares, then he can find a smaller prime \( p_2 \equiv 1 \pmod 4 \) which is not a sum of two squares as well. Applying the exact same argument, he can get an even smaller prime \( p_3 \equiv 1 \pmod 4 \) that's not a sum of two squares. Keep going and the primes that aren't sums of two squares get smaller and smaller until you get to \( 5 \). But this is a contradiction since \( 5 = 1^2 + 2^2 \).\(~\Box\)

What you just read is a particular type of proof by contradiction that Fermat developed and used extensively. A proof by contradiction in math is a proof that starts by assuming the opposite of what is being proven and then shows that that is impossible. The most popular example is proving \( \sqrt{2} \) is irrational. You first assume that \( \sqrt{2} = \frac{p}{q} \), i.e., \( \sqrt 2 \) is rational and then give a contradiction. The contradiction means \( \sqrt{2} \) can't be rational so it must be irrational. Fermat does the same thing: he assumes the opposite, i.e., that there is some prime \( p_1 = 4n+1 \) that is not a sum of two squares, and then comes to a contradiction: \( 5= 1^2 + 2^2 \) is not a sum of two squares. So the original assumption is false and all primes of the form \( 4n+1 \) are sums of two squares. The crux of the argument is in how to find a smaller prime of the same form that is still not a sum of two squares. Since Fermat does not explain how to do this, this is not a proof.

Fermat proved a lot of properties about natural numbers using the same idea: first assume some natural number didn't have the properties, and by some really clever argument, construct a smaller natural number that doesn't have the properties. By that same clever argument, construct smaller and smaller and smaller (... indefinitely) natural numbers that don't have the properties. But this is impossible since natural numbers can not get smaller and smaller forever — we don't have negative numbers! So this contradiction allows Fermat to conclude that all natural numbers have the given properties. Of course you can substitute “natural numbers” in this explanation with any subset of natural numbers. For example, in the outline given above, “natural numbers” has been substituted by “primes of the form \( 4n+1 \).” This type of proof by contradiction functions like an inverse of induction and Fermat called it proof by infinite descent. Fermat discusses it in detail in Letter 101, where the outline given above came from, and he lists various theorems he was able to prove with it. When I decided to write this post, I had about five Fermat theorems that I wanted to put in it. Imagine my shock when I saw that each one, except Fermat's little theorem, were listed in this letter as having been proven by infinite descent!

Now that we've seen the outline from Fermat, how was this theorem actually proven? Euler proved it in the course of two papers, E228 (1749) and E241 (1750), and his proof did use infinite descent. Although the proof uses infinite descent, it doesn't follow Fermat's outline and I am not sure if there's a proof that indeed follows Fermat's outline; you can read a summary of Euler's proof here. The following is a point I will return to again: Fermat mentions in a letter that he needed the Christmas theorem to prove another theorem, the polygonal number theorem, and in the papers in which Euler gave this proof, he was actually trying to prove one case of the latter theorem. He never managed to prove it but at least we got a complete proof of the Christmas theorem.

Let's talk about Fermat's polygonal number theorem then. One type of polygonal numbers has already shown up in my blog before: Euler's pentagonal number theorem, which is a completely unrelated theorem although it was proven the same year (see E244). Before I get into Fermat's theorem, let me describe polygonal numbers.

Triangular numbers are numbers that arise from building triangles using dots layer-by-layer. Squares numbers will be numbers that arise from building squares layer-by-layer. Same thing for pentagonal numbers and pentagons, hexagonal numbers and hexagons, etc. See the following image for an illustration. And in general, when the polygons have \( k \) sides, I'll say “\( k \)-gonal numbers.”

Polygonal Number Theorem. All natural numbers \( n \) can be written as a sum of at most 3 triangular numbers, 4 squares, 5 pentagonal numbers, 6 hexagonal numbers, etc. In general, all natural numbers can be written as a sum of at most \( k \) \( k \)-gonal numbers.

Example 4. Let \( n = 14 \).

Triangular numbers \( (k=3) \): \( 14 = 1 + 3 + 10 \).

Square numbers \( (k=4) \): \( 14 = 1 + 4 + 9 \), the theorem says we need at most 4 and we used 3.

Pentagonal numbers \( (k=5) \): \( 14 = 1 + 1 + 12 \), the theorem allows repeating summands.

Note: Most of Fermat's claims appear in several of his letters. In this post, I've focused only on the very first letter in which a claim appeared and later letters will only be mentioned if he discussed its proof in them. I also cite the margin notes since I can't tell which between the letters and notes are oldest.

The earliest mention from Fermat of this theorem that I can find is in Letter 12 to Mersenne (Sept 1636). It is also a margin note in Diaphontus, Obs. 18., which could have been written even earlier. The theorem is mentioned again in Letter 74 (25 Sep. 1654) and this is where he said that he needed the Christmas theorem to prove it. Later again, he mentioned the \( k=4 \) case of the theorem in Letter 101 while listing theorems he'd proven using infinite descent. Euler never proved this case but he proved the following partial result in E242 (1750): any number is a sum of at most four squares if one allows the squares to be fractions. 20 years later, Lagrange would use Euler's ideas to complete the proof of the polygonal number theorem when \( k=4 \) and this case is now called Lagrange's four-square theorem. I've said Euler never proved this theorem a few times but, to be fair, two years after Lagrange's result, Euler published E445 (1772) and greatly simplified Lagrange's original argument. Does that count as having proven the theorem as well? That's a question for another day.

In 1796, Gauss proved the case \( k=3 \), i.e., that every natural number is a sum of at most 3 triangular numbers. According to wikipedia, this is sometimes called the Eureka Theorem because Gauss wrote “EUREKA! \( n = \Delta + \Delta + \Delta \)” in his diary the day he proved it. It is also an immediate consequence of another theorem that was published a year later: Legendre's three-square theorem, which is incidentally equivalent to Fermat's claim in Obs. 27. Even though Legendre was the first to publish a proof, the case is credited to Gauss since the diary entry is dated earlier. Finally, Cauchy proved the full polygonal theorem in 1813 by showing it is a consequence of the Eureka theorem.

Anyway, back to Fermat! So Fermat claimed to have proven, amongst other things, the Christmas theorem and Lagrange's four-square theorem using infinite descent. The eventual proofs indeed used the same technique. Fermat also said that the Christmas theorem was necessary for the polygonal theorem and Euler did have to prove the Christmas theorem before Lagrange could prove the four-square theorem. I'm tempted to believe he had these or similar proofs even though it took other mathematicians nearly two centuries to produce them. But Legendre's theorem seems to use deep ideas on the theory of quadratic forms which was developed in the 18th century. The thing that works in Fermat's favor is he did recognize the difficulty of the problem and the [potential] importance of his ideas. Here's what he wrote after stating the theorem in Obs. 18:

My translation from French. I can't give the proof here as it depends on various abstruse mysteries of the science of number. I intend to dedicate an entire book on the subject and thereby accomplish surprising and unprecedented progress in this area of arithmetics.

It is a shame that no such book was ever written. So the two centuries don't inspire as much doubt if Fermat thought he needed an entire book to express the ideas in his proof. But it is rather surprising that he never once mentioned these ideas in his letters. So do we now take Fermat's word for it? Maybe not since there's one claim which he made that turned out to be false. Not false in the earlier sense that he made some implicit assumption but just flat out false.

False Conjecture. \( 2^{2^n}+1 \) is a prime number for all \( n \).

Examples & Euler's Counterexample. For \( n = 0, 1, 2, 3, 4 \), we have

\( 2^{2^0}+1 = 3, \) \( 2^{2^1}+1 = 5, \) \( 2^{2^2}+1 = 17, \) \( 2^{2^3}+1 = 257, \) \( 2^{2^4}+1 = 65537 \) are all primes.

However, \( 2^{2^5}+1 = 4294967297 = 641 \cdot 6700417 \) is not a prime number. Euler gave this counterexample in E026, the same paper I cited earlier in which Euler independently conjectures Fermat's little theorem.

The earliest mention of the conjecture that I found was in Letter 43 (Aug. 1640) to Frenicle and the latest mention was in Letter 96 (June 1658) to Digby; on the other hand, it never appeared in the margins of Arithmetica. He had verified it for the given examples but \( 2^{2^5} + 1 \) might have been too big for him to factor. However, this conjecture is not worth mentioning just because it was (the only example of him being) wrong (that I could find). It is the way he stated it in letters. In Letter 43, Fermat said he believed it to be true but that he had no proof of it. Again in Letter 96, written 18 years later, he admitted to having no proof of the statement. In this same letter, Fermat claims to have proofs of Christmas theorem, polygonal number theorem, and the next theorem I will be discussing. So for 18 years, Fermat differentiated the conjecture from his other statements. A year later, in Letter 101, Fermat seems to claim that he used infinite descent to prove the conjecture. But the conjecture is stated in a rather odd way and it can be argued that he was overstating his technique's importance to spark the interest of other mathematicians. So is it a coincidence that the one statement he continually admitted not being able to prove for 18 years was the only statement that was eventually disproven? But it is a fallacy to conclude that he had proofs for his theorems. Maybe he just had very good insight in the workings of numbers to come up with the right statements... On to the next Fermat theorem.

Theorem 6. No triangular number, except \( 1 \), is a fourth power.

This theorem is in Letter 96 and also at the end of Obs. 45 — the marginal note that contains his only known proof. At the end of giving the proof by infinite descent for his right-triangle theorem, Fermat says that he used the same process to prove this theorem. Euler proves it in E98 (1738) and I think it's only worth mentioning that Euler first proves a statement equivalent to the right-triangle theorem. Euler was basically following Fermat's footsteps. Now what is this theorem that we absolutely know that Fermat proved?

Right Triangle Theorem. There's no right-angled triangle with integer sides whose area is a square number.

Fermat never wrote the proof in his letters even though he was challenging others to prove it (and other equivalent statements) as early as Letter 12. In Letter 101, he gives this as the first example of theorems he was able to prove using infinite descent and this is his outline: Suppose you have a right-angled triangle with integer sides whose area is a square number. By Fermat-ian magic, you construct a smaller right-angled triangle with integer sides whose area is a square number, etc. This leads to a contradiction and so no such triangle existed in the first place. Fortunately for us, we do not have to guess what the Fermatian magic is. In Obs. 45, he writes out the proof and it does indeed match his outline. The Wikipedia article on this theorem has a similar proof if you want to see the magic.

While we're on the topic of infinite descent, I want to highlight a distinction between the two outlines of proofs by infinite descent. The right triangle theorem and theorem before it are negative statements since they're about the non-existence of objects with a given property. That is why they weren't followed with examples like all the other theorems before them. The method of infinite descent is well-suited for negative statements: assume that said objects exist, construct smaller objects, etc. and get a contradiction. But the Christmas theorem is an affirmative statement: it is about the existence of the property “is a sum of two squares.” Fermat explains in Letter 101 that it took him a while to figure out how to prove affirmative statements using the infinite descent. Looking at the dates: right triangle theorem appeared in Letter 12 (1636) and Christmas theorem in Letter 45 (1640). So assuming these dates are close to when the theorems were proven, then it did take a while for Fermat to adapt the technique for affirmative statements. Seeing Fermat explain the subtle differences in how to apply the technique is evidence to me that he did have the proofs for his theorems — he wasn't just spouting correct statements but was actually thinking about the subtleties in their proofs. I'll comeback to infinite descent again but for now let's talk about the one theorem that we all agree that Fermat had no proof for.

Last Theorem. For \( n \ge 3 \), \( x^n + y^n \not = z^n \) when \( x,y,z \) are positive integers.

The theorem is found in the infamous margin note, Obs. 2, where Fermat stated it and claimed to have a truly ingenious proof of it but didn't have enough room for it. I could be wrong but I don't think the theorem appears in its full generality in the letters. But I did find cases \( n=3, 4 \) used as challenges to other mathematicians. It can be shown that the right triangle theorem implies the \( n=4 \) case and so the proof of this is attributed to Fermat. Fermat lists the \( n=3 \) case in the infinite descent letter and it shouldn't come as a surprise that Euler's proof of it in E387 (1770) used infinite descent. Fermat's last theorem has a very long history and its eventual proof 300+ years later required deep results from outside of Number Theory. There's no way he had these ideas and, as no simpler (“elementary”) proof is believed possible, we think Fermat's claimed proof had an error; maybe he noticed a flaw in the proof and that's why he used cases \( n=3,4 \) and not the general statement in his letters. So I believe he definitely didn't have a proof for Fermat's last theorem, are there other theorems on this list? The next one is partially on it.

Pell's Equation. Let \( D \) be a nonsquare integer, i.e., \( D \not = n^2 \).

There is an algorithm which always finds (all?) infinitely many integer solutions to \[ x^2 - D y^2 = 1 \]

Example 6. Let \( D = 2 \) which is not a square.

\[ 1 = 3^2 - 2 (2^2) = 17^2 - 2 (12^2) = \ldots = x_n^2 + 2 y_n^2 \] Let \( x_1 = 3 \) and \( y_1 = 2 \). In general, if you have a solution \( (x_{n}, y_{n}) \), then you can construct another one \( (x_{n+1}, y_{n+1}) \) with this recursive formula: \[ \begin{aligned} x_{n+1} &= 3x_{n} + 4y_{n} \\ y_{n+1} &= 2x_{n} + 3y_{n}\end{aligned} \] Can you find one solution for \( D=3? ~ D= 61?~ D = 109? \)

Fermat was not the first, by any means, to ask this problem. In fact, unbeknownst to Fermat and his contemporaries, a 12th century Indian mathematician called Bhaskara II had solved the problem. Bhaskara had given an algorithm that produced a solution for any given nonsquare \( D \). It was known that a single solution led to infinitely many more via recursive formulas thanks to Brahmagupta's Identity — Brahmagupta was a 7th century Indian mathematician. However, Bhaskara didn't prove that his algorithm always worked. So there was an algorithm which worked for all inputs that had been given to it but no one had proven that it would never fail.

Centuries later, Fermat was challenging other mathematicians to find such an algorithm, implying he had one himself. In case they failed to find it, he also asked for solutions when \( D=61, 109 \) which would appear to be an easier problem. But there's a catch: the cases \( D=61, 109 \) have very large solutions, solutions that would be impossible to find by trial-and-error, solutions that essentially require an algorithm to generate them. The fact that these were the examples he gave in his letters is strong evidence that Fermat indeed had an algorithm to solve it; he must have used the algorithm to pick the hardest cases to suggest. When you look at the table of initial solutions for \( D=2, \ldots, 128 \) on wikipedia, you find that \( D=61, 109 \) have the two largest initial solutions!

Euler published an algorithm in E029 (1733) and E323 (1759) that was based on continued fractions. Although the presentation is different, this appears to be essentially the same algorithm as Bhaskara's. And just like Bhaskara, Euler didn't prove that the algorithm always worked. It was Lagrange who eventually proved in 1768 that this algorithm always produced a solution.

Let's return to the question I asked just before bringing up Pell's equation. Do I believe that he had a solution to this problem? It's hard to answer. For starters, he must have had an algorithm to help him pick those two hard cases of Pell's equation. And if I were to guess, I'd say he had the same algorithm as Bhaskara and Euler. But, this is where things get interesting, Fermat said in Letter 101 that he could prove the equation had infinitely many solutions using infinite descent. This could be interpreted multiple ways:

• He used infinite descent to prove that Bhaskara's algorithm worked. I just can't fathom how infinite descent could be used to prove this. And since I haven't even read Lagrange's proof, I can't make good judgement on what can and cannot prove the algorithm works.
• He used infinite descent to prove a different algorithm worked. My first concern still applies. It's easy to use infinite descent to show something doesn't exist; it's trickier but still possible to show something does exist; where do you even begin to show an algorithm works?
• He used infinite descent to prove there's always a solution. This is a little more manageable. It's an affirmative statement and so it won't be straightforward to prove but it's at least plausible. My guess is you start by assuming \( x^2 - Dy^2 = 1 \) has no integer solution and then creating smaller \( d \) so that \( x^2 - dy^2=1 \) has no integer solutions either, etc. Infinite descent then says this is impossible so \( x^2 - Dy^2 = 1 \) has a solution for all nonsquare \( D \). The issue here is proofs by contradiction are nonconstructive. Such a proof can tell you a solution exists but doesn't tell you how to find it. Yet Fermat insisted that others find an algorithm that produces a solution.

Searching around the web, I haven't been able to find anyone using infinite descent on Pell's equation. But in Fermat's defence, when he talked about Pell's equation in the letter, he said the problem was as difficult for him to prove as Lagrange's four square theorem. Of both theorems, he said:

My translation from French. There are some [questions] that demand new principles before using infinite descent and finding these principles is so difficult that it can't be done without extreme pain.

So on one hand, 300 years have passed and still no one has a proof of the theorem using infinite descent; on the other, Fermat had an algorithm and he claims he found it using infinite descent. Who am I to say he didn't? It is possible we still don't appreciate the full potential of this technique like Fermat did.

So how verstile was Fermat's method of infinite descent? Well, Fermat claimed to have proven a lot of theorems and he attributed the proofs of many of these to his method of infinite descent. In August 1659, Fermat wrote Letter 101 to Carcavi — he wanted to share his novel technique that he had found indispensable. After giving two outlines of how he used infinite descent to prove a negative satement (right triangle theorem) and then trickier affirmative statement (Christmas theorem), he listed several difficult theorems that he was able to prove using infinite descent:

1. Lagrange's four square theorem, the case \( k=4 \) for his polygonal theorem
2. Pell's equation (with algorithm) Fermat highlights these two for being extremely difficult to prove. *Is it a coincidence that it's Lagrange who proved both of these theorems?*
3. The case \( n=3 \) for his Last theorem
4. \( (5,3) \) is the only integer solution to \( x^2 + 2 = y^3 \).
5. \( (2, 2) \) and \( (11, 5) \) are the only integer solutions to \( x^2 + 4 = y^3 \).
6. \( (1, 1, 1) \) and \( (7, 2, 5) \) are the only integer solutions to the simultaneous equations: \[ \begin{aligned}x+1 &= 2y^2 \\ x^2 + 1 &= 2z^2 \end{aligned} \]

I think it would be an interesting project to track down how these were eventually proven. If the first published proof didn't employ infinite descent, is there a known infinite descent proof now?

1. Looking at proof of Lagrange's theorem on Wikipedia, they use a proof by contradiction with the well-order property of natural numbers. This is just a [modern reformulation](https://en.wikipedia.org/wiki/Minimal_counterexample) of infinite descent.
2. I've already voice my concerns on how to use infinite descent constructively. However, when I was reading about Euler's proof of Christmas theorem I came across a very interesting thing. So backtracking a little bit, Fermat asked Pascal in Letter 74 (25 Sep. 1654) whether he could show that primes of the form \( 4n+1 \) were sums of two squares and also give an algorithm that produces those two squares. For example, if you know that \( 53 = 4\cdot 13 + 1 \) is prime then can you split it into two squares, \( 53 = 2^2 + 7^2 \), without trial-and-error? So we know Fermat solved Christmas theorem using infinite descent but we have the same issue: how did he use infinite descent to get an algorithm. Edwards (pg. 55) gives an excellent explanation of how Euler's proof by infinite descent can be modified to be constructive. The relevant pages are available on Google Books so I encourage you to check it out if you're interested. So the problem doesn't seem as impossible anymore. Perhaps an infinite descent proof that Pell's equation has a solution can be modified into an algorithm that produces the solution(s).
3. Euler's proof of this used infinite descent. Not much else to say on this that I haven't already.
4. I don't know much about this problem and didn't really research it. When I googled “infinite descent and Pell's equation,” I found this related question on StackExchange (SE). According to it, the theorem is proven using unique factorization of \( {\mathbb Z}[\sqrt 2] \); I don't know the proof but I'll take their word for it. The SE question is specifically asking if there's a known infinite descent proof, just like I am here. There doesn't seem to be one but a user gave several ideas on how you could try to come up with one.
5. Don't know anything about this either. According to that same SE user, there is no known infinite descent proof for this either.
6. Don't know anything about this. Honestly, I only think its true cause Fermat said so and, by now, I trust his judgement...

I think that's a good place to end this exposition.

It's really amazing how my attitude changed over the course of researching and writing this post. I've been writing this for a week and I think you can sense the change in the writing itself. At the beginning, I was very skeptical of why Fermat had so many things named after him in Number Theory if we only have one proof from him. I appreciate the contribution of someone asking the right questions and making the right conjectures, but is that enough to get the recognition Fermat gets in Number Theory? But by the end of the post, I am writing things like, “I only think its true cause Fermat said so.”

Bibliography

Oeuvres de Fermat. Web — This a collection with 4 volumes in it. Vol. 1 is where you'll find his margin notes in their original Latin. Vol. 2 contains his letters, these are in a mix of French and Latin. Vol. 3 has the French translations of all the Latin documents in the first volumes. I didn't really use Vol. 4 so I don't know what's in it. The webpage that I've linked to has all these volumes as PDF. The page also has English translations for a few documents. If you'd rather read the books online, then they're also hosted on archive.org.

Heath, Thomas Little. Diophantus of Alexandria: A Study in the History of Greek Algebra. Cambridge University Press, 1910. Web — Fermat had a copy of the Latin version of this book in which he wrote all his margin notes. This book is the English translation and it talks about Fermat's work in the introduction, notes, and supplement.

The Euler Archive. Web — This is the go to website for anything Euler-related. It is an archive of everything Euler published. If English translations exist, then they'll be here. I reference E387 at some point in the post; E387 is actually his book Elements of Algebra. There's an English translation of it available as a free eBook on Google Books.

Weil, André. “Review: MS Mahoney, The Mathematical Career of Pierre de Fermat.” Bull. Amer. Math. Soc. 79.6 (1973): 1138-1149. Web

Burton, David. A History of Mathematics: An Introduction. McGraw-Hill Companies, 2011.

Edwards, Harold M. Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. Vol. 50. Springer-Verlag, 1977.