Odd Prime Divisors of Sum of Squares

[omega16]

Can anyone help me with this question?

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

 

[matt grime]

Have you reduced a^2+b^2 mod anything?

 

[omega16]

No, still can't figure out how to start this proof. Could you please teach me how to do it? Thank you very much.

 

[shmoe]

What do you know about primes that are congruent to 1 mod 4?

 

[matt grime]

My question still stands. Did youi try to reduce this mod anything? Surely that is the first thing to do since the question is about mod arithmetic. So reduce it mod anything that seems reasonable and play around with what's left. Then tell us what you think. The purpose of this is website is not to do it for you, nor to teach you by doing it for you, but to get you to do things for yourself. You've been given the starting point, now what have you done?

 

[omega16]

That is what I can think of:

Since p|(a^2+b^2), so a^2+b^2≡ 0 (mod p) and a^2 ≡ -b^2 mod p

 

[shmoe]

So far so good. Any other manipulations you can do to that?

Did you think about the question I asked?

 

[omega16]

No , don't know what to go on next?

Does the below theorem useful for go on my prove?

if p is prime, the equation x^2 ≡ - 1 mod p has solution iff p ≡ 1 mod 4

 

[shmoe]

Does the below theorem useful for go on my prove?

if p is prime, the equation x^2 ≡ - 1 mod p has solution iff p ≡ 1 mod 4

Yes, very usefull.

You have a^2=-b^2 mod p

Is there anyway you can move the b over to the other side? When is such an operation valid?

 

[omega16]

thank you very much. I have solved this question.