# Legendre symbol simplification

I saw a simplification using the Legendre symbol which said $$\left(\dfrac{19}{29}\right) = \left(\dfrac{10}{19}\right) = \left(\dfrac{2}{19}\right) \cdot \left(\dfrac{5}{19}\right) = -1.$$ My question is how did they get $\left(\dfrac{19}{29}\right) = \left(\dfrac{10}{19}\right)$ and finally that $\left(\dfrac{2}{19}\right) \cdot \left(\dfrac{5}{19}\right) = -1$?

• Quadratic reciprocity and multiplicativity of the Legendre symbol. – Jack D'Aurizio Jul 26 '16 at 20:31
• As an alternative, $$\left (\frac{19}{29} \right)= \left( \frac{10}{29} \right) = \left( \frac{-3}{29}\right)= -1$$ since $29$ is not a prime of the form $3k+1$. – Jack D'Aurizio Jul 26 '16 at 20:33

For the first question

$$\left(\dfrac{19}{29}\right) = \left(\dfrac{29}{19}\right) = \left(\dfrac{10}{19}\right)$$ since $29$ is $1$ mod $4$.

For the second, $$\left(\dfrac{5}{19}\right) = \left(\dfrac{19}{5}\right) = \left(\dfrac{-1}{5}\right) = 1$$ since $5$ is $1$ mod $4$ and $$\left(\dfrac{2}{19}\right) = -1$$ because $19$ is $3$ mod $8$. (http://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/the-quadratic-character-of-2)

This seems a combination of quadratic reciprocity and the Legendre formula.

The Legendre formula states that $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}}\mod p$, giving $\left(\dfrac{2}{19}\right) = -1$ and $\left(\dfrac{5}{19}\right) = 1$. These give the second equality. (Since 19 isn't that large, it's quite possible to do determine by hand if 2 or 5 are quadratic residues).

The quadratic reciprocity law states that $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{{\frac{p-1}{2}}{\frac{q-1}{2}}}$. Since $\left({\dfrac{29}{19}}\right) = \left({\dfrac{10}{19}}\right)$, the first equality you asked for follows. (Notice that since $\left(\dfrac{p}{q}\right)$ and its reciprocal are $\pm1$, dividing or multiplying by one of them yields the same result.)

• I am wondering why it turns out that $14$ is the least such power of $19$ such that $19$ to a power is $-1$ modulo $29$. We have $19^{\frac{29-1}{2}} = 19^{14}\equiv -1 \pmod{29}$. Is there a reason for that? – John Ryan Jul 26 '16 at 20:41
• I'm afraid I don't quite follow you. Any power of $19$ is equivalent to $0$ modulo 19, isn't it? – HSN Jul 26 '16 at 20:46
• Sorry, I meant modulo $29$. – John Ryan Jul 26 '16 at 20:46
• I'm not sure I know about any reason why it should be the least power. What we do know for sure, thanks to Fermat's little theorem and due to the fact that $29$ is prime, is that $a^{28}\equiv 1\mod 29$ for all $a$. As a result $a^{14} \equiv \pm 1\mod 29$ for all $a$. It could just as well have been the case that $7$ would've fulfilled the requirement you mention, since it's a diviser of $28$ as well. – HSN Jul 26 '16 at 20:53