Fermat’s Last Theorem (mod p)

homer_3d

 

(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.

Complete Graph

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.

RedBlueColouring

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

R(3,3,3)

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).

Advertisements
This entry was posted in Combinatorics, Number Theory, Uncategorized and tagged , , , , , , . Bookmark the permalink.

2 Responses to Fermat’s Last Theorem (mod p)

  1. Jeremy Alm says:

    This proof of FLT mod p seems to be incorrect. If n does not divide p-1, then the resulting equivalence classes are singletons. In fact, k (the number of equivalence classes) depends on p, and that’s a problem. It can be fixed by taking p sufficiently large and congruent to 1 mod n (and Dirichlet’s theorem assures us that there are infinitely many such primes).

    • Jeremy Alm says:

      Never mind — it’s not that the equivalence classes are singletons, but that there is only one equivalence class. My mistake.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s