2
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Quadratic reciprocity and multiplicativity of the Legendre symbol. $\endgroup$ – Jack D'Aurizio Jul 26 '16 at 20:31
  • $\begingroup$ 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$. $\endgroup$ – Jack D'Aurizio Jul 26 '16 at 20:33
1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Ryan Jul 26 '16 at 20:41
  • $\begingroup$ I'm afraid I don't quite follow you. Any power of $19$ is equivalent to $0$ modulo 19, isn't it? $\endgroup$ – HSN Jul 26 '16 at 20:46
  • $\begingroup$ Sorry, I meant modulo $29$. $\endgroup$ – John Ryan Jul 26 '16 at 20:46
  • $\begingroup$ 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. $\endgroup$ – HSN Jul 26 '16 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.