# Sum of two squares

• Sep 11th 2006, 08:26 AM
beta12
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.
• Sep 11th 2006, 09:30 AM
ThePerfectHacker
Quote:

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 :rolleyes: )
• Sep 12th 2006, 09:40 AM
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.
• Sep 12th 2006, 09:54 AM
ThePerfectHacker
Quote:

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 :D )
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
• Sep 12th 2006, 10:28 AM
beta12
Hi perfecthacker,

Why do "a" & "b" have the form 4k, 4k+1, 4k+2 , and 4k+3?
• Sep 12th 2006, 10:35 AM
CaptainBlack
Quote:

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
• Sep 12th 2006, 10:54 AM
beta12
Thank you very much.

I got this question fully.