## Fermat’s Last Theorem (mod p)

(Picture from the Simpsons episode “Treehouse of Horror VI” where Homer enters the world of 3D.
Try entering the numbers in your hand calculator)

The statement of the perhaps most famous mathematics problem over the past few centuries should not have slipped past many people with some interest in mathematics.
I am of course talking about Fermat’s Last Theorem (FLT) which was finally resolved by Andrew Wiles in 1995 in what is considered one of the most remarkable mathematical achievements of modern day.
FLT is one of those problems whose statement is so often understood by anybody on the street, but is very difficult to prove. The amount of machinery that lies behind Wiles proof is astonishing (more so in algebraic geometry than pure number theory).

As a reminder I will state FLT and then begin discussing the contents of this post.

Fermat’s Last Theorem:

Let $n \in \mathbb{Z},\;n > 2$.Then there exists no $x,y,z \in \mathbb{Z},\;x,y,z \neq 0$ s.t $x^n + y^n = z^n$.

In this post I wanted to treat a related question.
Is FLT true over finite fields of characteristic p?
That is, can we refute the existence of non-trivial integer solutions to $x^n + y^n = z^n$ if we work $(mod\;p)$ where $p$ is a prime number?

The answer is No.
You can probably immediately spot counterexamples such as $2^3 + 2^3 \equiv 1^3 (mod\;3)$.

More remarkably however, given $n \in \mathbb{Z},\;n \geq 1$ there exists non-trivial solutions to $x^n + y^n = z^n$ $(mod\;p)$ for every prime $p$ sufficiently large.
Schur came up with this result while trying to prove FLT.
This result probably gives some idea as to why FLT was so hard to prove since it shows one cannot simply consider congruences like one often does when working with other types of Diophantine equations.

Another interesting fact about this result is that it can be proved using both Fourier Analysis and Ramsey Theory. This may seem rather surprising since Ramsey Theory is combinatorics (a field dealing with countable discrete structures) whereas Fourier Analysis revolves around function approximation using continuous trigonometric functions, and both are used here to prove a number theoretic result. This shows just how differently mathematics problems can be approached if one can find a suitable phrasing in whichever language is being used.

I would like to focus on the latter proof using Ramsey Theory.
So what is Ramsey Theory?
The slogan for Ramsey Theory is basically that any sufficiently large structure, no matter how disordered, contains some element of order. For graph structures one usually likes to look at edge colourings and say something about specific subgraphs where all edges are of the same colour.

Let’s make an important definition to make this more precise:

Definition (Ramsey Number):

A graph on $n$ vertices is complete (denoted $K_n$) if every pair of vertices is connected by a unique edge.

Let $R(r,s)$ denote the smallest number such that for any red/blue edge-colouring of $K_{R(r,s)}$ there exists either a monochromatic red subgraph $K_r$ or a monochromatic blue subgraph $K_s$.

The numbers $R(r,s)$ are called Ramsey Numbers.

We may also define Generalized Ramsey Numbers $R(r_1,...,r_k)$ as the smallest number such that any $k-colouring$ of $K_{R(r_1,...,r_k)}$ contains at least one monochromatic subgraph $K_{r_i}$ of colour $i$ for some $1 \leq i \leq k$

I have omitted one crucial detail: How do we know $R(r,s)$ is well-defined?
This is exactly what Ramsey’s Theorem asserts, that this number exists in the first place.
The proof is not actually very difficult, one proceeds by proving an upper bound on $R(r,s)$. One can then show well-definedness of the generalized Ramsey number by proving the recursive inequality $R(r_1,...,r_k) \leq R(r_1,...,r_{k-2}, R(r_{k-1},r_k))$ and using the well-definedness of $R(r_{k-1},r_k)$ as part of an inductive argument.
I will however omit the details of the proof and move on to the main result of this post.
Before we get there we need an intermediate theorem which seemingly has little to do with our goal:

Theorem (Schur):

Let $k > 1$.

Then $\exists N \in \mathbb{Z}$ s.t $n \geq N \Longrightarrow \forall k-colourings\; of\;\{1,...,n\},\;\exists\; x,y,z \in \{1,...,n\}$ of same colour s.t $x+y=z$

Proof:

A k-colouring of $\{1,...,n\}$ is the same as a function $C:\{1,...,n\} \rightarrow \{1,...k\}$.

Take $n \geq R(3,...,3)\; (k\;times)$.

Then by Ramsey’s Theorem we are guaranteed that any k-colouring of $K_n$ contains a monochromatic triangle.

Define a k-colouring on the edges of $K_n$ by $e = (i,j) \mapsto C(|i-j|)$.

The existence of a monochromatic triangle in $K_n$ then means $\exists a,b,c \in \{1,...,n\}$ s.t $C(|a-b|) = C(|b-c|) = C(|c-a|)$

W.l.o.g assume $a < b < c$ and put $x = b-a,\; y = c-b, z = c-a \in \{1,...,n\}$.

Then $x + y = z$ as desired where $C(x) = C(y) = C(z)$.

Main Theorem:

Let $n \in \mathbb{Z},\; n > 1$.

Then there exists a prime $p_0$ s.t for every prime $p \geq p_0$

$x^n + y^n \equiv z^n (mod\;p)$ has a non-trivial integer solution i.e a solution where $x,y,x \not\equiv 0 (mod\;p)$

Proof:

The proof depends on a key fact which is much easier to understand if you know some Group Theory.

The fact is that every integer in $\{1,...p-1\}$ can be written as some (multiplicative) power of a fixed integer in the same set $(mod\;p)$.
[in other words $\mathbb{Z}_p^*$ is a cyclic group]

To informally look at this another way (without directly using notions from Group Theory), define $A_n := \{ a^n\;(mod\;p): a \in \{ 1,...,p-1\} \}$.

The reason we want $p$ to be a prime instead of just any integer is that we need to make sure we have no zero divisors i.e we need to ensure there exists no non-zero $a,b$ s.t $ab = 0 (mod\;p)$.
One of the reasons for this is that we would like to make the definition below:

Define an equivalence relation $\sim$ on $\{ 1,...,p-1\}$ by:
$x \sim y \Longleftrightarrow x \equiv yt \;(mod\;p)$ for some $t \in A_n$.
(You can check this is well defined for $p$ prime)

The so called equivalence classes are defined as $a_iA_n := \{ a_it\;(mod\;p) : t \in A_n \}$ for some representatives $a_1,...,a_k \in \{ 1,...,p-1\}$

A standard fact from set theory tells us that equivalence classes on a set form a partition
$\{ 1,...,p-1\} = a_1A_n \cup ... \cup a_kA_n$.
After all, every integer in $\{ 1,...,p-1\}$ must belong to some equivalence class and you can check that they do not intersect.

Now we can start colouring the set $\{ 1,...,p-1\}$.

Define the colouring $C:\{ 1,...,p-1\} \rightarrow \{1,...k\}$ by $C(x) = i$ iff $x \in a_iA_n$.

By Schur’s Theorem $\exists N \in \mathbb{Z}$ s.t $p \geq N \Longrightarrow \exists a,b,c \in \{ 1,...,p-1\}$ s.t $a+b \equiv c\;(mod\;p)$ with $C(a)=C(b)=C(c)$.

In other words we can find non-trivial $a,b,c \in \{ 1,...,p-1\}$ s.t $a,b,c \in a_iA_n$ for some $i$ so that $a = a_ix^n, b=a_iy^n,c=a_iz^n$ for some $x,y,z \in \{ 1,...,p-1\}$ and $a_ix^n+a_iy^n \equiv a_iz^n\; (mod\;p)$

Since $a_i$ and $p$ are co-prime we may divide away $a_i$ to get $x^n+y^n \equiv z^n\; (mod\;p)$.

Exercise 1( R(3,3) -Easy ):

Prove that $R(3,3) = 6$.

Hint: Think of the pigeonhole principle for the upper bound

(I was actually asked to prove this myself in one of my undergraduate admissions interviews, though it was stated differently in terms of friends and strangers instead of as a Ramsey Number)

Exercise 2( R(3,3,3) -Hard ):

Prove that $R(3,3,3) = 17$.

(Note: Proving this was one of the questions in a past IMO competition, again stated very differently).