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

1. ### arfa branecall me arfValued 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

3. ### arfa branecall me arfValued 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

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

7. ### arfa branecall me arfValued 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 branecall me arfValued 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. ### NehushtanRegistered 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$.

$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 branecall me arfValued 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. ### NehushtanRegistered 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 branecall me arfValued 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}}$