1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A number theory question

  1. Sep 7, 2006 #1
    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. jcsd
  3. Sep 7, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Have you reduced a^2+b^2 mod anything?
     
  4. Sep 11, 2006 #3
    No, still can't figure out how to start this proof. Could you please teach me how to do it? Thank you very much.
     
  5. Sep 11, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What do you know about primes that are congruent to 1 mod 4?
     
  6. Sep 11, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    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?
     
  7. Sep 12, 2006 #6
    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
     
  8. Sep 12, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

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

    Did you think about the question I asked?
     
  9. Sep 12, 2006 #8
    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
     
  10. Sep 12, 2006 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  11. Sep 12, 2006 #10
    thank you very much. I have solved this question.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A number theory question
Loading...