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 = 1² + 2² , 13 = 2^{2 +}  3² ,

17 = 1² + 4² , 29 = 2² + 5² ;

 

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 = x² + 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)² + (2n+1)²

                        =  4m²+ 4n²+ 4m+ 4n+ 1+ 1

                        = 4(m²+ n²+ m+ n) + 2 = 4k + 2 (say)

 

Case 2: Both are even

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

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

                        =  4m²+ 4n²+ 8m+ 8n+ 4+ 4

                        = 4(m²+ n²+ 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)² + (2n+2)²

                        =  4m²+ 4n²+ 4m+ 8n+ 1+ 4

                        = 4(m²+ n²+ 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 x² + y².

 

 

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 a^p-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 + y²r/x = (r/x)(x² + y²) 

 

Since p is prime, r/x =1 and p = (x² + y²) 

 

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) = ∑ ₀^4k 2C1 a = p**2 – p = p(p-1) = 0|mod p;

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

 

And,

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

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

 

And,

Sum(3)=∑ ₀^4k  [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 ∑ ₀^4k  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

 

 

A Mathematicians Apology

A Mathematicians Apology is the title of a book written by the great mathematician G H Hardy. Yes the same person who discovered our Ramanujan. Here he used the word apology in the meaning of defense, justification or explanation, not so much as regret or confession.  Here are some passages from the book for the benefit of my friends.

 

- – - “The beauty of a mathematical theorem depends a great deal on its seriousness, as even in poetry the beauty of a line may depend to some extent on the significance of the ideas which it contains. I quoted two lines of Shakespeare as an example of the sheer beauty of a verbal pattern, but

 

After life’s fitful fever he sleeps well

 

seems still more beautiful. The pattern is just as fine, and in this case the ideas have significance and the thesis is sound, so that our emotions are stirred much more deeply. The ideas do matter to the pattern, even in poetry, and much more, naturally, in mathematics; but I must not try to argue the question seriously.” – - -

 

- – - “It will be clear by now that, if we are to have any chance of making progress, I must produce example of ‘real’ mathematical theorems, theorems which every mathematician will admit to be first-rate. And here I am very handicapped by the restrictions under which I am writing. On the one hand my examples must be very simple, and intelligible to a reader who has no specialized mathematical knowledge; no elaborate preliminary explanations must be needs; and a reader must be able to follow the proofs as well as the enunciations. These conditions exclude, for instance, many of the most beautiful theorems of the theory of numbers, such as Fermat’s ‘two square’ theorem on the law of quadratic reciprocity. And on the other hand my examples should be drawn from the ‘pukka’ mathematics, the mathematics of the working professional mathematician; and this condition excludes a good deal which it would be comparatively easy to make intelligible but which trespasses on logic and mathematical philosophy.” – - -

 

- – - “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 = 1² + 2² , 13 = 2^{2 +}  3² ,

17 = 1² + 4² , 29 = 2² + 5² ;

 

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.” – - -

 

- – - “I wrote a great deal during the next ten years, but very little of any importance; there are not more than four or five papers which I can still remember with some satisfaction. The real crisis of my career came ten or twelve years later, in 1911, when I began my long collaboration with Littlewood, and in 1913, when I discovered Ramanujan. All my best work since then has been bound up with theirs, and it is obvious that my association with them was the decisive event of my life. I still say to myself when I am depressed, and find myself forced to listen to pompous and tiresome people, ‘Well, I have done one the thing you could never have done, and that is to have collaborated with both Littlewood and Ramanujan on something like equal terms.’ It is to them that I owe an unusually late maturity: I was at my best a little past forty, when I was a professor at Oxford. Since then I have suffered from that steady deterioration which is the common fate of elderly men and particularly of elderly mathematicians. A mathematician may still be competent enough at sixty, but it is useless to expect him to have original ideas.” – - -

 

Yes, Mr. Hardy discovered Ramanujan. But did he do enough to save him from his ailments? I am not so sure, even after reading two biographies on Ramanujan. Apart from obtaining an FRS, Ramanujan did not get anything substantial from the UK government. The fact remains, that if not for Hardy, Ramanujan might well have died as a clerk in Madras Port Trust.

 

(By the way, Fermat’s Two Square Theorem looks nice and simple. But why should its proof also be nice and simple? A subject for a future blog.)

 

Ramanujan, The greatest ever Indian mathematician.

Only recently I read a biography “The Man Who Knew Infinity”, on Ramanujan, the greatest ever Indian mathematician, . It was amazing and poignant at the same time.
Some of the problems mentioned in the book, revved up my aging mind. I tried to prove one of his equations. I am sure this being one of the simpler equations of Ramanujan, many would have solved it during the last century itself. Still I feel elated that I was able to share a very small part of his genious. Ofcourse, unlike Ramanujan, I had a formal education upto master’s level in engineering in one of the IITs. If only we had IITs in those days ……..?
I am attaching  two proofs for Ramanujan’s equation, one of which I call as Derivation. I feel very happy to share the same with my readers.
Happy to be associated with great minds of India,
regards to all,
L V Nagarajan

 

Solution for the Problem by Sri Ramanujan

 

1.      To Prove

(x + n + a) =  √[ax +(n+a)² +x√[a(x+n) +(n+a)² + (x+n)√[a(x+2n) +(n+a)² + (x+2n) √etc  ….

Proof

Let A_x = √[ax +(n+a)² +x√[a(x+n) +(n+a)² + (x+n)√[a(x+2n) +(n+a)² + (x+2n) √etc  ….

Then, We may write

A_x = √[ax +(n+a)² +x A_{x+ n}]

 

i.e.       A_x² = [ax +(n+a)² +x A_{x+ n}]

 

 

i.e.       A_x² – (n+a)²  = [ax + x A_{x+ n}] = [ a + A_{x+ n} ] x

 

 

i.e.       [A_x - (n+a)] . [A_x + (n+a)] = [ a + A_{x+ n} ] x

 

 

i.e.       [A_x - (n+a)] / x = [ a + A_{x+ n} ] / [A_x + (n+a)] = k (say) —– (1)

 

Hence,             A_x = kx + n + a;   And so, A_{x+ n} =  k(x + n) + n + a ———(2)

 

Substituting in the second part of eqn(1) above,

[a + k(x + n) + n + a] / [kx +n +a + n+ a] = k

i.e        xk² + (2n + 2a – x – n) k – (n + 2a) = 0

i.e.       xk² + (n + 2a – x) k – (n + 2a) = 0

i.e.       (xk + n + 2a) (k – 1) = 0, giving the values, k =1 or kx = – n – 2a

Substituting in (2)

            A_x = x + n + a , or A_x = – a, (not admissible)

Hence proved

 

 

2.      The above is a proof. Let us call the following as a derivation.

 

Derivation

(x +n+ a)    =  √ [ (x + n + a)² ]

= √ [ x² + ( n + a)² + 2x(n + a) ]

= √ [ ax + x² + ( n + a)² + x(2n + a) ]

= √ [ ax + ( n + a)² + x(x + n +n + a) ]  ——–(i)

 

Following as per Eqn (i) above, we may write:

(x+n +n + a) = √ [ a(x+n) + ( n + a)² + (x+n)(x + 2n + n + a) ] ——(ii)

 

From Eqns (i) and (ii), we can recursively write:

(x +n +a) = √[ax + ( n + a)² + x√[a(x+n) + ( n + a)² + (x+n)√[a(x + 2n) + (n+a)² + (x+2n)√…

 

Hence Derived

 

 

3.      To Find the value of  √[1+2√[1+3√[1+4√[1+5√[1+ …….

 

(n+1)² = n² + 2n + 1

= 1 + n(n+2)

i.e.

n + 1 = √ [1 + n(n+2]]

Hence we may write,

3 = √ [1 + (2 x 4)] and

4 = √ [1 + (3 x 5)] and

5=  √ [1 + (4 x 6)],  etc

 

Hence,

3= √[1+2√[1+3√[1+4√[1+5√[1+ …….

 

 

 

L V Nagarajan

01 July 2008