# Artificial truth

## The more you see, the less you believe.

[archives] [latest] | [homepage] | [atom/rss]

# Proof of Fermat's sandwich Sun 24 April 2016 — download

Thanks to a complicated week-end, I ended up reading a book called Fermat's Last Theorem (don't buy it, it's a piece of crap, wrong on the historical, and on the mathematical side: for a book about history and maths, this is a nice performance.).

Everywhere in the book, it's written that Fermat was known to not write complete proofs (or proofs at all) for his theorems, challenging his colleagues to prove them. This was of course getting on everyone's nerve.

In the book, I stumbled upon this line:

Fermat shown that 26 is the only number sandwiched between a perfect square number ($$25 = 5^2$$) and a perfect cubic one ($$27 = 3^3$$) The proof is interesting but non-trivial.

And then the book moves on to something else.

It was a bit super pissed off, so I decided to find the proof by myself. But because I didn't want to get stuck, I ask a more mathematic-versed friend of mine about this project, and he answered me that albeit this is a complex problem, he knew that I was capable of doing it.

Like almost every post on this blog, this article will be detailed enough so everyone, even with a light background, can understand what's going on. The obvious hint in our pocket, here we go:

We can rewrite the theorem as:

%% \forall x \in \mathbb{N}^{*}; x-1 = a^2; x+1 = b^3 \Rightarrow x = 26; a = 5; b = 3 %%

or

%% 5^2 < 26 < 3^3 %%

If we subtract the two equalities ($$x - 1 = a^2$$ and $$x + 1 = b^3$$), we obtain $$-2 = a^2 - b^3$$ This type of equation is called a diophantine equation (and this one is a Mordell curve). Unfortunately for us, Yuri Matiyasevich proved that there is no general algorithm to solve them. This was the 10th Hilbert problem by the way. There is some modern research about how to solve them, but I'm quite sure that Fermat managed to find an easier way.

That being said, time to use our hint: a complex problem. If you don't know what a complex number is, you should go read about them, but if you're lazy, all you need to know to understand this article is that $$i^2 = -1$$

We can factorise our first equation:

%% \begin{aligned} -2 &= x^2 - y^3\\ y^3 &= x^2 + 2\\ &= (x + i\sqrt{2})(x - i\sqrt{2}) \end{aligned} %%

Now, we've got two interestingly similar part in our equation: $$(x + i\sqrt{2})$$ and $$(x - i\sqrt{2})$$.

What about trying to find their GCD to see how they're related to each other? Because if they are mutual primes, we'll likely be able to simplify a bit our equation. Mutual primes are number that aren't sharing a single factor except the number $$1$$

It's interesting to note that we're now playing in the imaginary quadratic field $$\mathbb{Z}[\sqrt{-2}]$$.

An algebraic integer of the form $$a+b\sqrt(D)$$ where $$D$$ is squarefree forms a quadratic field. Squarefree means that its prime decomposition contains no repeated factors.

This means that the numbers that we're going to manipulate are of the form $$a + bi\sqrt{2}$$ (or $$a + b \sqrt{-2}$$ , because $$i^2 = -1$$, remember?). Anyway, what is important here, is that $$2$$ is a Heegner number, meaning that numbers in our fieidl have unique factorization.

This is the case on our usual domain $$\mathbb{N}$$ also known as the naturals ring, thanks to the fundamental theorem of arithmetic . But this is not the case, for example in $$\mathbb{Z}[i\sqrt{5}]$$ where you can write $$6 = 2\cdot{}3$$ but also $$6 = (1 + i\sqrt{5})(1 - i\sqrt{5})$$.

Ok, back to business, computing the GCD of $$x+i\sqrt{2}$$ and $$x-i\sqrt{2}$$:

%% \begin{aligned} gcd(x+i\sqrt{2}, x-i\sqrt{2}) &= gcd(x+i\sqrt{2}, (x+i\sqrt{2})-(x-i\sqrt{2}))\\ &= gcd(x+i\sqrt{2}, 2i\sqrt{2})\\ &= gcd(x+i\sqrt{2}, \sqrt{2}^{2}\cdot{}i\sqrt{2})\\ &= gcd(x+i\sqrt{2}, i\sqrt{2}^3) \end{aligned} %%

The trick used in the first line is that when you compute $$gcd(A, B)$$ you can add as much $$A$$ as you want to $$B$$, it doesn't change the result: $$gcd(A, B) = gcd(A, B+NA)$$

We're now going to use quadratic residues: $$q$$ is called a quadratic residue modulo $$n$$ if $$\exists x, x^2 \equiv q (mod n)$$. It is going to help up determining the parity of $$x$$ and $$y$$: we're going to use some reductio ad absurdum in a particular congruence ring $$\mathbb{Z}/n\mathbb{Z}$$ (namely $$\mathbb{Z}/8\mathbb{Z}$$) that still holds in $$\mathbb{N}$$, since there is an isomorphism between $$\mathbb{Z}/n\mathbb{Z}$$ and $$\mathbb{Z}$$.

If $$x$$ is even, it can be seen as $$n * 2$$, with $$n \in \mathbb{N}$$. In $$\mathbb{Z}/8\mathbb{Z}$$, meaning that: $$x^2 = y^3 - 2 (mod 8) \Leftrightarrow x^2 = 8n^3 -2 (mod 8) \Leftrightarrow x^2 = -2$$, which is impossible in $$\mathbb{Z}$$, so $$y$$ must be odd.

Since $$y^3 = x^2 + 2$$ (or $$y^3 - x^2 = 2$$ if you prefer), $$x$$ and $$y$$ have the same parity, meaning that both are odd, so $$gcd(x+i\sqrt{2}, x-i\sqrt{2}) = 1$$

Great, we proved that $$x-i\sqrt{2}$$ and $$x+i\sqrt{2}$$ are relative primes, time to go back to our original equation : $$y^3 = (x + i\sqrt{2})(x - i\sqrt{2})$$

We can express $$y$$ as a unique decomposition of prime factors $$p_1, p_2, p_3, ...$$, like $$y = p_1^{a_1} \cdot p_2^{a_2} \cdot ... = \prod_{i \in I}p_i^{a_i}$$ meaning that $$y^3 = \prod_{i \in I}p_i^{3\cdot{}a_i}$$

Since $$x + i\sqrt{2}$$ and $$x - i\sqrt{2}$$ are relative primes, they don't share a single factor: $$\forall i,j ; z_j \neq z_i$$

We can combine those two facts by saying that there is a non-empty set $$J \subset I$$ so that $$x \pm i\sqrt{2} = (\prod_{j \in J}p_j^{\alpha{}_j})^3$$.

So $$x \pm i\sqrt{2}$$ is a cube in $$\mathbb{Z}[i\sqrt{2}]$$ :

%% \begin{aligned} x + i\sqrt{2} &= (a + bi\sqrt{2})^3\\ &= a^3 + 3a^2bi\sqrt{2} - 6ab^2 - 2\cdot{}b^3\cdot{}i\sqrt{2}\\ &= (a^3 - 6ab^2) + (3a^2b - 2b^3)\cdot{}i\sqrt{2}\\ &= (a^3 - 6ab^2) + b\cdot{}(3a^2 - 2b^2)\cdot{}i\sqrt{2} \end{aligned} %%

We can now split the equality in two part: $$x = a^3 - 6ab^2$$ and $$b\cdot{}(3a^2 - 2b^2) = 1$$.

From the second part, we can deduce that $$b = \pm 1$$ and $$3a^2 - 2b^2 = \pm 1$$. Because $$b = \pm 1$$ $$b^2 = 1$$, so $$3a^2 = 2 \pm 1$$, and since $$3a^2 = 1$$ is impossible, the only solution is $$a = \pm 1$$

From the first one, we can now write that $$x = a^3 -6ab^2 = 5$$ and the only positive outcome possible is $$x = 5$$.

Back to our initial equation $$x^2 + 2 = y^3$$ we can now replace $$x$$ with $$5$$, giving us $$25 + 2 = y^3 \Leftrightarrow y = \sqrt{27} \Leftrightarrow y = 3$$

And we just proved that the only solution to $$y^3 = x^2 + 2$$ is $$x = 5$$ and $$y = 3$$. ■

Now I don't know if I should say thank you or fuck you to Fermat for keeping me busy my whole week-end. This article was also a great excuse to give a try to mathjax, a 62MB (yes.) javascript display engine for mathematics.

edit: Thanks to Armavica for spotting some mistakes that are now fixed