# A number theory question

#### 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

Homework Helper
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

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

#### matt grime

Homework Helper
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

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

#### 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

Homework Helper
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?

#### omega16

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