Quadratic reciprocity 'problem'

Discussion in 'Physics & Math' started by arfa brane, Mar 29, 2013.

  1. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    Using quadratic reciprocity, calculate the Legendre symbol: \( \;(\frac {31} {43}) \).

    I have:
    \( \;(\frac {31} {43})\; =\; (\frac {43} {31}) (-1)^{\frac {43-1} {2} . \frac {31-1} {2} }\; =\; -(\frac {43} {31})\;=\; -(\frac {12} {31})\;=\; -(\frac {2} {31})(\frac {2} {31})(\frac {3} {31}) \;=\; -(\frac {3} {31}) \;=\; -(\frac {31} {3})(-1)^{\frac {31-1} {2}. \frac {3-1} {2}}\;=\; -(\frac {31} {3})(-1)\;=\; -(\frac {1} {3})(-1)\;=\; -(-1)^{\frac {3-1} {2}}\;=\; 1 \).

    Is there a problem with the last three equalities?

    Ed: I get it; \( -(\frac {1} {3})(-1)\;=\; (\frac {1} {3})\;=\; 1 \). Since \( (\frac {1} {3})\;=\; (\frac {1^2} {3}) \)
     
    Last edited: Mar 29, 2013
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    Determine the odd primes p for which 15 is a quadratic residue modulo p.

    We must have gcd(15,p) = 1 (since 15 and p are coprime?). We want to know for which integers X

    \( X^2 \equiv \;15\; (mod\; p) \)​

    By Euler's criterion

    \( 15^{\frac {p-1} {2}}\; \equiv\; 1\; (mod\; p) \)​

    What's a good way forward from here? This isn't an assignment btw, these are exercises we're supposed to work on.
     
    Last edited: Mar 29, 2013
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. Nehushtan Registered Member

    Messages:
    29
    Nope. \(0^2\equiv15\,\pmod3\) and \(0^2\equiv15\,\pmod5\).


    Nope. We want to know for which odd primes \(p\) there exist integers \(X\) such that \(X^2\equiv15\,\pmod p\). We know at this point that \(p=3\) and \(p=5\) are two of them.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    Well, doesn't it come down to whether p divides 15? I can see that since 49 = 15 + 2(17), we have a winner with 7[sup]2[/sup] and p = 17.

    So X = 7 is one more; and X = 17 - 7 is another. Do I have to like, check each prime ≥ 15, and is there an easier way than adding 15 to some multiple as I did above?
     
  8. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    Aha. I might be getting the hang of this.

    Since we have:
    \( X^2 \equiv \;a\; (mod\; p), \;\;a = 15 \)​

    And
    \( a^{\frac {p-1} {2}}\; \equiv\; 1\; (mod\; p) \)​

    But
    \( a^{\frac {p-1} {2}}\; \equiv\; (\frac {a} {p})\; (mod\; p) \)​

    Then I can show that if:
    \( (\frac {15} {17})\; =\; 1 \)​

    p = 17 has two solutions, and similarly for larger primes? Seems like an awful lot of work.
     
  9. Nehushtan Registered Member

    Messages:
    29
    As I said before we are NOT finding how many solutions \(X^2\equiv15\,\pmod p\) there are. We only want to find odd primes \(p\) such that there is at least one \(X\) satisfying \(X^2\equiv15\,\pmod p\). It doesn’t matter how many such \(X\) there are for a given \(p\) (FYI there are always an even number of such \(X\) if they exist – see below).

    In other words, given an odd prime \(p\), what is the answer to the question: “Is 15 a quadratic residue modulo \(p\)?” We want to find those \(p\) for which the answer is “yes”.

    Let’s take 11. We note that \(2^2\equiv15\,\pmod{11}\) – so the answer when \(p=11\) is “yes”. \(\left(\dfrac{15}{11}\right)=1\).

    What about 13? Let’s check:


    \(1^2=1\not\equiv15\,\pmod{13}\)

    \(2^2=4\not\equiv15\,\pmod{13}\)

    \(3^2=9\not\equiv15\,\pmod{13}\)

    \(4^2=16\not\equiv15\,\pmod{13}\)

    \(5^2=25\not\equiv15\,\pmod{13}\)

    \(6^2=36\not\equiv15\,\pmod{13}\)​

    None of these squares is congruent to 15 modulo 13. Hence the answer when \(p=13\) is “no”: \(\left(\dfrac{15}{13}\right)=-1\).

    By the way, why did we stop at \(6^2\) above? The answer is that given any integer \(r\), \(1\leq r\leq p-1\), we have \(r^2\equiv(p-r)^2\,\pmod p\) – so to check quadratic residues by brute force, we only need to check the squares \(1^2,2^2,\ldots,\left(\frac{p-1}2\right)^2\). Note also that as \(p\) is odd, \(r\ne p-r\). This explains why there are always an even number of solutions (if any exist) to the congruence \(X^2\equiv15\,\pmod p\).
     
    Last edited: Mar 30, 2013
  10. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    What I'd like to be able to figure out is something about quadratic reciprocity that lets you answer questions like the one above without brute force.

    What we want is odd primes p for which \( (\frac {15} {p})\;=\; 1 \). We know that \( (\frac {15} {p})\;=\; (\frac {3} {p})(\frac {5} {p}) \), so we want the RHS to equal 1.

    But this must mean that \( (\frac {3} {p})\;=\;(\frac {5} {p}) \). Now what?

    Ed: hang on, if p = 3 or p = 5, then \( (\frac {3} {p})(\frac {5} {p}) \;=\; 0 \). Ok, those are the trivial solutions.
     
  11. Nehushtan Registered Member

    Messages:
    29
    This is what I’ve found: If \(p\) is an odd prime and \(\gcd(p,5)=1\) then:

    \(\displaystyle\left(\frac5p\right)\ =\ \left\{\ 1\ \text{if}\ p\equiv1,9\,\pmod{10} \\ {\ } \\ -1\ \text{if}\ p\equiv3,7\,\pmod{10} \right.\)​

    I believe this can be proved using Gauss’s lemma. Unfortunately I can’t find a similar formula for \(\left(\frac3p\right)\), only \(\left(\frac{-3}p\right)\).
     
  12. arfa brane call me arf Valued Senior Member

    Messages:
    7,713
    Well, we also have that: \(\left(\frac3p\right)\;=\;\left(\frac5p\right) \).

    And that: \(\left(\frac3p\right)\;=\; \left(\frac p3\right)(-1)^{\frac{p-1} {2}} \)
     

Share This Page