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.

Printable View

- September 11th 2006, 08:26 AMbeta12Sum 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. - September 11th 2006, 09:30 AMThePerfectHacker
There are two ways to prove it, the

**Im**PerfectHacker 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),

Since -b^2 is a quadradic residue of a^2 we have,

(-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: ) - September 12th 2006, 09:40 AMbeta12
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. - September 12th 2006, 09:54 AMThePerfectHacker
Yes,

**Im**PerfectHacker (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 - September 12th 2006, 10:28 AMbeta12
Hi perfecthacker,

Why do "a" & "b" have the form 4k, 4k+1, 4k+2 , and 4k+3? - September 12th 2006, 10:35 AMCaptainBlack
- September 12th 2006, 10:54 AMbeta12
Thank you very much.

I got this question fully.