Computing Legendre symbol of a (p = prime number raised to prime number) mod p?

Question

Example:

What is the Legendre Symbol $ (\frac{3^{24671}}{105953}) $?

Since ($\frac{3}{105953}$) $= -1$ and the exponent p = prime = $24671$ is odd, would this mean the answer would be -1?

Please advise.

Thanks!

Answer 1

By quadratic reciprocity we have $\left(\frac{3}{105953}\right)=\left(\frac{105953}{3}\right)=\left(\frac{2}{3}\right)=-1$, since $105953\equiv 1\bmod 4$, and therefore $$ \left(\frac{3^p}{105953}\right)=\left(\frac{3}{105953}\right)^p=\left(\frac{2}{3}\right)^p=(-1)^p=-1. $$