LinkBack URL
About LinkBacks
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.
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.Originally Posted by beta12
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)
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
  |
