Fermat’s Two Squares Theorem

In one of my earlier blogs, I gave extracts from the book, ‘A Mathematicians Apology’ written by the great mathematician G H Hardy. Yes the same person who discovered our Ramanujan. In this book he talks about Fermat’s Two Squares Theorem, as below:

 

– – – “Another famous and beautiful theorem is Fermat’s ‘two square’ theorem. The primes may (if we ignore the special prime 2) be arranged in two classes; the primes

5, 13, 17, 29, 37, 41,

which leave remainder 1 when divided by 4, and the primes

3, 7, 11, 19, 23, 31,

which leave remainder 3. All the primes of the first class, and none of the second, can be expressed as the sum of two integral squares: thus

 

5 = 12 + 22 , 13 = 22 +  32 ,

17 = 12 + 42 , 29 = 22 + 52 ;

 

but 3, 7, 11, and 19 are not expressible in this way (as the reader may check by trial). This is Fermat’s theorem, which is ranked, very justly, as one of the finest of arithmetic. Unfortunately, there is no proof within the comprehension of anybody but a fairly expert mathematician.” – – –

 

Fermat’s Two Square Theorem looks nice and simple. But why should its proof also be nice and simple? I have given a proof here which I think is simple enough for all to appreciate.

 

In number theory, formal statement of Pierre de Fermat‘s theorem on sums of two squares goes as below:

An odd prime p is expressible as

p = x2 + y;  with x and y as integers, if and only if p =1 (mod 4).

 

Proof-1

Sum of two squares:

 

Case 1: Both numbers are odd

2m+1 and 2n+1

Sum of squares = (2m+1)2 + (2n+1)2

                        =  4m2+ 4n2+ 4m+ 4n+ 1+ 1

                        = 4(m2+ n2+ m+ n) + 2 = 4k + 2 (say)

 

Case 2: Both are even

2m+2 and 2n+2 ( to avoid zero)

Sum of squares = (2m+2)2 + (2n+2)2

                        =  4m2+ 4n2+ 8m+ 8n+ 4+ 4

                        = 4(m2+ n2+ 2m+ 2n + 2) = 4k + 0 (say)

 

Case 3: One is odd and the other is even

2m+1 and 2n+2 ( to avoid zero)

Sum of squares = (2m+1)2 + (2n+2)2

                        =  4m2+ 4n2+ 4m+ 8n+ 1+ 4

                        = 4(m2+ n2+ m+ 2n + 1) + 1 = 4k + 1 (say)

 

Hence any number of the form 4k + 3 can never be a sum of two squares. This includes primes also. Hence one part of Fermat’s theorem is proved.

 

As per the second part of the theorem, the prime numbers of the form 4k+1 will definitely qualify to be sum of squares as per case-3 above. But we have to prove that they are always of the form x2 + y2.

 

 

Proof-2

In this proof, I am using another theorem by Fermat known as Fermat’s Little Theorem, which is given below along with proof.

 

Fermat’s Little Theorem.

Let p be a prime which does not divide the integer a, then ap-1 = 1 (mod p).

 

Proof.

Start by listing the first p-1 positive multiples of a:

a, 2a, 3a, … (p -1)a

Suppose that ra and sa are the same modulo p.

Then, (r – s)a is divisible by p

Since prime p does not divide a, (as stated above), it should divide r-s.

This means r = s, (mod p), which cannot be true.

So the p-1 multiples of a above are distinct and nonzero,

Hence, they must be congruent to 1, 2, 3, …, p-1 (mod p),  in some order.

Multiply all these congruencies together and we find,

a*.2a*.3a*.…*.(p-1)a = 1*2*.3*.…*.(p-1) (mod p)

 

or, a(p-1)(p-1)! = (p-1)! (mod p).

 

 

Divide both sides by (p-1)!

 

            a(p-1) =  1 (mod p).

 

Hence proved.

 

 

By Fermat’s Little Theorem, for a prime number p, and for any number a not divisible by p,

 

a ** (p-1) = 1 (mod p),

 

 

If p=1 (mod 4), then p must be of the form p = 4k + 1

 

Hence we may write, for any prime p of the form p = 4k + 1, and for any number a not divisible by p, by Fermat’s Little Theorem,

           

            a ** (4k) = 1 (mod p),

 

i.e.      

a ** 2k = +1 or -1 (mod p), depending on the value of a. [Note: -1 (mod p) = p-1]

 

Now let us take one value of a, for which, (a ** 2k) = -1 (mod p)

(The proof for existence of such a value for ‘a’ is given in the end)

So, (a**2k + 1) is divisible by p, = f*p, say.

(i.e.) (a**k + j1)(a**k – j1) = f*p

 

Let us say p is a prime in complex domain also. Then p divides at least on of the complex numbers on the left hand side. Then it should divide its conjugate also. Then it should divide the difference also. i.e. p divides ‘j2’, which cannot be true. Hence p is not a prime in complex domain. This means p has complex factors though it is a prime in real numbers domain.

Let,

(p + j0) = (x +jy) (r+ js)

= (xr-ys) + j(yr+xs)

i.e. (yr+xs)= 0

i.e. yr = -xs, and s = -yr/x

and p = xr – ys = xr + y2r/x = (r/x)(x2 + y2) 

 

Since p is prime, r/x =1 and p = (x2 + y2) 

 

Hence proved

 

 

Examples 

 

a. Consider p =13 = 4*k + 1, k=3

2 ** 2k = 2**6 = 64 = -1|mod p

(2**2k + 1) = divisible by p = 5 * 13

(2**3 + j1)(2**3 – j1) = 5 * 13

Substituting, 5 = (2-j1)(2+j1) and 13 = (3+j2)(3-j2)

We get, (8 + j1) (8 – j1)= (2 – j1)[(3+j2)(3-j2)] (2 + j1)

 

 

b. Consider p=17 = 4*k + 1, k = 4

3**2k = 3**8 = 6561 = -1|mod p

3**2k + 1 = divisible by p = 386 * 17

i.e. (3**4 + j1)(3**4 – j1) = (19+j5) [(4-j1)(4+j1)] (19 – j5)

 


Proof for existence of a value for ‘a’ such that (a ** 2k) = -1 (mod p)

 

Consider a taking values a = 1 to p-1, none of them divisible by p.

Consider the sum,

4k                           4k

∑ (a+1)**(n+1) = ∑  a**(n+1)  +  (4k+1)**(n+1)

a=0                       a=1  

 

 

We can write,

(a+1)**(n+1)

          = a**(n+1) + (n+1)C1 a**n +  (n+1)C2 a**(n-1) + ……+  (n+1)Cn a + 1

 

So, the above summation may be re-written as

4k                          

∑[(n+1)C1 a**n +  (n+1)C2 a**(n-1) + ……+  (n+1)Cn a] + (4k+1)

a=0

                                                                                    = (4k+1)**(n+1)

Realising that p = 4k+1, we get,

4k                          

∑[(n+1)C1 a**n +  (n+1)C2 a**(n-1) + ……+  (n+1)Cn a] = p**(n+1) – p = 0|mod p

a=0                             

In short we may write,            Sum(n) = p**(n+1) – p = 0|mod p

 

The above equation is true for all values of n, n = 1 to n.

 

Hence,

Sum(1) = ∑ 04k 2C1 a = p**2 – p = p(p-1) = 0|mod p;

                                     i.e  04k  a = p(p-1)/2 = 4k(4k+1)/2: a known result.

 

And,

Sum(2) = ∑ 04k [ 3C2 a**2 + 3C1 a] = p**3 – p = p(p**2 – 1) = 0|mod p

                        Using the above result for Sum(1), we get 04k  a**2 = 0|mod p

 

And,

Sum(3)=∑ 04k  [4C3 a**3+ 4C2 a**2 + 4C1 a] = p**4 – p = p(p**3 – 1) = 0|mod p

                        Using above Sum(1) and Sum(2), we get 04k  a**3 = 0|mod p

 

And so on . . . . . .

 

The particular case of interest to us is, when n = 2k.

Using same successive logic as above, we get,

                        a=0 4k  a**2k = 0|mod p  – – – – – – – – – –  A

 

As stated at the start, by Fermat’s Little Theorem,

            a ** (4k) = 1 (mod p),

 

Hence,

a ** 2k = +1 or -1 (mod p), depending on the value of a.

Equation A above means, (a ** 2k)|mod p, equally assumes

both values of +1 and -1, for ‘a’ varying from 1 to 4k.

 

Thus proved

 

 

Advertisements

Tags: ,

2 Responses to “Fermat’s Two Squares Theorem”

  1. Arkaprava Says:

    Really interesting sir…could u suggest me any advancement in this process then?

  2. Valady L Swaminathan Says:

    Wonderful Nagarajan Amazed at this collection

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


%d bloggers like this: