A number theory question

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

Science Advisor
Homework Helper
9,392
3
Have you reduced a^2+b^2 mod anything?
 
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

Science Advisor
Homework Helper
1,993
1
What do you know about primes that are congruent to 1 mod 4?
 

matt grime

Science Advisor
Homework Helper
9,392
3
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?
 
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

Science Advisor
Homework Helper
1,993
1
So far so good. Any other manipulations you can do to that?

Did you think about the question I asked?
 
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

Science Advisor
Homework Helper
1,993
1
omega16 said:
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?
 
thank you very much. I have solved this question.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top