# Thread: Sum of two squares

1. ## Sum of two squares

Do you know how to do this proof?

Suppose (a , b)=1 . Prove that if p|(a^2+b^2) then p ≡ 1 (mod 4).
Note: p is any odd prime.

2. Originally Posted by beta12
Do you know how to do this proof?

Suppose (a , b)=1 . Prove that if p|(a^2+b^2) then p ≡ 1 (mod 4).
Note: p is any odd prime.
There are two ways to prove it, the ImPerfectHacker method by examining each case. Or ThePerfectHacker method which is more elegant. Since I am who I say I am I am going to do it my way.

You have,
a^2+b^2≡0(mod p)
Thus,
a^2≡-b^2(mod P)
Thus, the Legendre Symbol (I presume you learned them by now),
(-b^2/p)=1
Thus,
(b^2/p)(-1/p)=1
But,
(b^2/p)=1
Thus,
(-1/p)=1
That is a famous case and only happens when,
p≡1 (mod 4)
---
This looks greatly similar to Fermat's theorem about expressing 4k+1 primes as a sum of two unique squares.
The proof of that is much more complicated (I wonder how Fermat proved it )

3. Hi perfecthacker,

The perfecthacker's way of prove is simple and nice. I like your way very much.

Do you have the other way to prove this question? Honestly, until now , I still haven't learnt Legendre symbol yet.

4. Originally Posted by beta12
Hi perfecthacker,

The perfecthacker's way of prove is simple and nice. I like your way very much.

Do you have the other way to prove this question? Honestly, until now , I still haven't learnt Legendre symbol yet.
Yes, ImPerfectHacker (my evil twin brother, wait I am the evil twin )
Would do it like this.

Divide the prove into cases. (Divison Algorithm)
'a' can have the form 4k,4k+1,4k+2,4k+3
Thus,
'a^2' can only be 4k,4k+1

'b' can have the form 4k,4k+1,4k+2,4k+3
Thus,
'b^2' 4k,4k+1

The different possible sums between 'a^2+b^2' are,
4k,4k+1,4k+2
Since 'p' divides them and is odd it cannot be 4k,4k+2
Thus, the only possible form of 'a^2+b^2' is 4k+1.

The prime 'p' can have two forms 4k+1,4k+3
Now, a number of the form 4k+3 cannot divide a number of the form 4k+1 because they are different forms.
Thus, p=4k+1

5. Hi perfecthacker,

Why do "a" & "b" have the form 4k, 4k+1, 4k+2 , and 4k+3?

6. Originally Posted by beta12
Hi perfecthacker,

Why do "a" & "b" have the form 4k, 4k+1, 4k+2 , and 4k+3?
because every number leaves a remainder of 0, 1, 2 or 3 when divided
by 4. (the k's are not both the same for a and b)

RonL

7. Thank you very much.

I got this question fully.