# A number theory question

1. Sep 7, 2006

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

2. Sep 7, 2006

### matt grime

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

3. Sep 11, 2006

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

4. Sep 11, 2006

### shmoe

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

5. Sep 11, 2006

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

6. Sep 12, 2006

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

7. Sep 12, 2006

### shmoe

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

8. Sep 12, 2006

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

9. Sep 12, 2006

### shmoe

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?

10. Sep 12, 2006

### omega16

thank you very much. I have solved this question.