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}) \)
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.
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.
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?
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.
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\).
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.
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)\).
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}} \)
