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!

Quadratic Residues

  1. Apr 2, 2006 #1
    I have this problem Ive been looking at for about 6 hours. It requires me to find all primes p such that 3 is a quadratic residue (mod p).

    All I could come up with is that every prime p ending in a 1 makes 3 a QR mod p. But this came after using excel and computing all primes. Surely there must be an easier way (assuming that my assumption is correct). The question does give a hint to use the Quadratic reciprocity law, but I have no idea what that is! :redface:
     
  2. jcsd
  3. Apr 2, 2006 #2
    Looking up that law wouldn't be a bad idea, don't you think? :smile:
     
  4. Apr 2, 2006 #3
    This is my version of the QRL, there may be others written differently.

    [tex]\mbox{Let }p\mbox{ and }q\mbox{ be distinct odd prime numbers. Then}[/tex]

    [tex](p/q)(q/p) = (-1)^{(p-1)(q-1)/4}}[/tex]
     
    Last edited: Apr 2, 2006
  5. Apr 2, 2006 #4
    The first thing I did was realize that the question was also asking that

    [tex] 3 \mbox{ is a Quadratic Residue } \Leftrightarrow 3^{\frac{p-1}{2}} \equiv 1(\mod p)[/tex]

    which means that all primes p such that 3 is a QR mod p will be a solution to the above congruence. So I started testing

    p=3
    [tex]3^1 = 3 \equiv 0(\mod 3)[/tex]
    p=5
    [tex]3^2 = 9 \equiv 4(\mod 5)[/tex]
    p=7
    [tex]3^3 = 27 \equiv 6(\mod 7)[/tex]
    p=11
    [tex]3^5 = 243 \equiv 1(\mod 11)[/tex]

    I was doing all the calculations in excel, and when I filled the columns in, I got equivalent to 1 mod p whenever my prime p ended in a 1.

    But I realize this method used only Euler's Criterion, nowhere did I use the QRL.
     
    Last edited: Apr 2, 2006
  6. Apr 2, 2006 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What did you get for 13? 41? Something is wrong with your calculations if you went this far and ended up with that conclusion.

    In any case, a finite number of calculations like this would never be able to prove a general result. It can point towards a general conjecture, but not prove it.

    Try using the law of quadratic reciprocity. It lets you turn a question about whether 3 is a quadratic residue mod p to a question about whether p is a quadratic residue mod 3 (and there's a simple congruence critera for this).
     
  7. Apr 2, 2006 #6

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    Let a and b be odd numbers. Then:

    (a/b) = (b/a) if a = 1 (mod 4) or b = 1 (mod 4)
    ........= -(b/a) if a = b = 3 (mod 4)

    Also, if p is an odd prime, a and b are integers, then

    (a/p)(b/p) = (ab/p)

    Of course, you also know that:

    (a/p) = ([a modulo p]/p)

    So with all these facts, you should be able to find the answer.
     
  8. Apr 3, 2006 #7
    You're absolutely right, my aim in doing that was to find a pattern which could motivate a possible line of attack in solving it. Unfortunately it didnt work, as we all now know.

    Ok, so now I have to determine whether or not a prime p is a QR mod 3.

    The Legendre symbol [itex](3/p)[/itex] equals 1 if 3 is a QR mod p right?

    Then Euler's criterion says that if [itex](3/p) = 1[/itex] then

    [tex]3^{(p-1)/2} \equiv 1(\mod p)[/tex]

    Then the QRL says that if [itex]3,p[/itex] are odd primes, and if [itex]3,p \equiv 3(\mod 4)[/itex], then

    [tex](3/p) = -(p/3)[/tex]

    Working backwards now, we have that if [itex](p/3) = 1[/itex] then

    [tex]p^{(3-1)/2} \equiv 1(\mod p)[/tex]

    which equals

    [tex]p\equiv 1(\mod p)[/tex]

    So p is a QR mod 3 if [itex]p\equiv 1(\mod 3)[/itex]

    This looks sketchy to me, I may have forgotten a negative sign too. hmmm Am I close?
     
    Last edited: Apr 3, 2006
  9. Apr 3, 2006 #8

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    yes, and -1 if it's not.

    No need for Euler's criterea here.

    Yes. Another case to consider is when p is 1 mod 4.

    This goes both ways, but there's no need to use Euler's critera. 1 is a QR mod 3 and 2 is not, so it's clear which primes mod 3 are quadratic residues.

    So if p=3 mod 4 and p=1 mod 3, is 3 a QR mod p or not? And the other cases?
     
  10. Apr 3, 2006 #9
    So p=1,7,13,19,etc... could be QR because they are all congruent to 1 mod 3, is this right?
     
  11. Apr 3, 2006 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Quadratic residues mod p, yes. if a=b mod p then (a/p)=(b/p)
     
  12. Apr 3, 2006 #11
    Where did "if [itex]p\equiv 3(\mod 4)[/itex]" come from?
     
    Last edited: Apr 3, 2006
  13. Apr 3, 2006 #12

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    When you applied the law of quadratic reciprocity you had assumed that p=3 mod 4, you have to consider the other case as well.
     
  14. Apr 3, 2006 #13
    Ok, so I have two cases:

    1.

    [tex]p \equiv 1(\mod 3)[/tex]
    [tex]p \equiv 3(\mod 4)[/tex]

    2.

    [tex]p \equiv 1(\mod 3)[/tex]
    [tex]p \equiv 1(\mod 4)[/tex]

    and using both cases togther I should be able to find exactly what p should be, instead of an (infinite) list of possible primes like I had before?
     
  15. Apr 3, 2006 #14

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What if p=2 mod 3?

    You need more cases, you have to consider what p is mod 3 and what it is mod 4, 2 possibilities for each.
     
  16. Apr 3, 2006 #15
    But I found that p=1(mod 3). And the only restrictions I have imposed from the QRL are that p=3(mod 4) and p=1(mod 4). What other restrictions are there? I havent said anywhere that p=2(mod 3).
     
  17. Apr 3, 2006 #16

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    No you didn't! You found that when (p/3)=1 you must have p=1 mod 3. But you arbitrarily imposed this condition (p/3)=1, why couldn't it have been -1? actually looking back if you were trying to force (3/p) to be 1 then you wanted (p/3)=1 then you should have looked at (3/p)=-1 (this was when you were in the case p=3 mod 4).

    There's a couple of things you need to know about to find (3/p),

    1)how (3/p) relates to (p/3). this is entirely determined by p=1 or 3 mod 4

    2)what is (p/3)? this is entirely determined by p=1 or 2 mod 3

    Hence the 4 cases. These will cover all primes
     
  18. Apr 3, 2006 #17
    STEP 1.

    Find all primes p such that 3 is a QR (mod p)

    <==> (by the QRL)

    Find all primes p such that p is a QR (mod 3)

    STEP 2.

    When is p a QR (mod 3)?

    p is a QR mod 3 precisely when (3/p) = 1.

    STEP 4

    The QRL says that if 3 and p are odd primes then

    1. (3/p) = (p/3) iff p=1(mod 4)

    OR

    2. (3/p) = -(p/3) iff p=3(mod 4)

    STEP 4.

    Take (3/p) = (p/3) (when p=1(mod 4))

    Then (3/p) = (p/3) = p^((3-1)/2) = 1(mod p)

    => p = 1(mod p)

    STEP 5.

    Take (3/p) = -(p/3) (when p=3(mod 4))

    Then -p=1(mod p) => p=2(mod p)
     
    Last edited: Apr 3, 2006
  19. Apr 3, 2006 #18
    So to answer your questions:

    1. (3/p) is related to (p/3) in two ways, each of which has its own restriction.

    (3/p) = (p/3) iff p=1(mod 4)
    (3/p) = -(p/3) iff p=3(mod 4)

    2. What is (p/3)? Not sure yet...
     
  20. Apr 3, 2006 #19

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Remember if a= b mod 3 then (a/3)=(b/3)
     
  21. Apr 3, 2006 #20
    Since [itex](p/3) \equiv p(\mod 3)[/itex], then let [itex]a = (p/3)[/itex], and [itex]b=p[/itex], then from your last posted identity we have

    [tex]((p/3)/3)=(p/3)[/tex]

    Im not sure if this is what you wanted.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Quadratic Residues
Loading...