# Congruencies application

Kindly read the following carefully, before generalizing.

1) If $(a, p) = 1$ and $p$ is some odd prime. Then the Legendre symbol $$\left(\frac ap\right)$$ is defined to be equal to $1$ if $a$ is a quadratic residue of $p$ and is equal to $-1$ if $a$ is a quadratic non-residue of $p$.

2) For a prime of the form $5k+2$, the statement $$5^{\frac{5k+1}{2}}\equiv (5k+1) \pmod{ 5k+2}$$ is true or not?

How to generalize or justify the above statements?

-

Do you know about quadratic reciprocity? In this case, it says that, if $5k+2$ is prime, then (since 5 is prime and $5\equiv1\pmod4$) 5 is a quadratic residue modulo $5k+2$ if and only if $5k+2$ is a quadratic residue modulo 5. But working modulo 5, $5k+2$ is the same as 2, and (it's easy to see) 2 is not a quadratic residue modulo 5. Working our way back, $5k+2$ is not a quadratic residue modulo 5, and 5 is not a quadratic residue modulo $5k+2$. As Berci notes, this implies $5^{(5k+1)/2}\equiv-1\equiv5k+1\pmod{5k+2}$.

-

Take $a=5$ and $p=5k+2$. Then we want to show that $a^{\frac{p-1}{2} }=-1$.
Indeed $a^{\frac{p-1}{2}}=\left( \frac{a}{p}\right)=\left( \frac{5}{p}\right)=\left( \frac{p}{5}\right)=\left(\frac{2}{5}\right)=-1$

-
Does this add anything to what I posted earlier? –  Gerry Myerson Sep 27 '12 at 10:43

For any $a\not\equiv 0 \pmod p$, by Fermat's little, $a^{p-1}\equiv 1 \pmod p$, so, since $p$ is prime, $a^{\frac{p-1}2}\equiv \pm 1$. By the way, this equals exactly $\left(\displaystyle\frac ap\right)$: one direction is easily seen: if $a\equiv b^2 \pmod p$, then $1\equiv b^{p-1}\equiv a^{\frac{p-1}2}$, and the other direction goes by some counting..

So, you state that $5$ is never a quadratic residue mod $p=5k+2$... I'm not certain it is true.

-