2
$\begingroup$

I'd really love your help with the following problem: For prime $p$, $p= 5 (\bmod 8)$, and $a$ such that $(\frac{a}{p})=1$ (Legendre symbol): I need to show that $a^{(p-1)/4}$is either $1$ or $-1$ and that if it's 1, so $x=a^{(p+3)/8}$ is a solution for $x^2 \equiv a(\bmod p)$.

For the first part, Can I look on $x^4 \equiv 1(p)$, and tell that if $a^{(p-1)/4}$ is not 1 or -1 I get contradiction to Fermat theorem, but is it enough? This equation can have up to 4 solutions, what else should I use? I don't see how the other information helps.

From the information given I know that $x^2 \equiv 2 (\bmod p)$ is not solvable (Does it help?)

For the second part of the question, Isn't it just that $(a^{(p+3)/8})^2\equiv a^{(p-1)/4}a \equiv a \equiv a(\bmod p) $?

Thanks a lot.

  • 0
    can just use the equation $x^2 \equiv 1(\bmod p)$ for showing that first claim?2012-06-24

2 Answers 2

3

Using Euler's criterion we know that:

$a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \bmod p$.

So:

$a^{\frac{p-1}{2}} \equiv 1 \bmod p$.

Now using difference of two squares we see that:

$(a^{\frac{p-1}{4}} + 1)(a^{\frac{p-1}{4}} - 1) \equiv 0 \bmod p$.

The fact that $p$ is prime now tells us that $a^{\frac{p-1}{4}} \equiv \pm 1 \bmod p$.

For the second part notice that we needed to know that $\left(\frac{a}{p}\right) = 1$ for there to actually exist a solution to $x^2 \equiv a \bmod p$. You have checked that if this is the case then $a^{\frac{p+3}{8}}$ would be a solution.

However, is $\frac{p+3}{8}$ necessarily an integer? In this case yes because $p \equiv 5 \bmod 8$. So this was an important condition too.

5

Let $p=8k+5$. Since $a$ is a QR of $p$, by Euler's Criterion we have $a^{4k+2}\equiv 1\pmod{p}$. It follows that $a^{2k+1}\equiv \pm 1\pmod{p}$. That settles the first part of the question.

If $a^{2k+1}\equiv 1\pmod{p}$, then $a^{2k+2}\equiv a\pmod{p}$, and therefore $a^{k+1}$ is a solution of the congruence $x^2\equiv a\pmod{p}$. That settles the second part.

Remark: You did not ask, but what about if $a^{2k+1}\equiv -1\pmod{p}$? Perhaps that is the next question!

Use the fact that you noted, that $2$ is a NR of $p$, since $p$ is of the form $8k+5$. It follows that $2^{4k+2}\equiv -1\pmod{p}$. Using $a^{2k+1}\equiv -1\pmod{p}$, we conclude that $2^{4k+2}a^{2k+1}\equiv 1\pmod{p}.$ Multiply by $a$. We find that $(2^{2k+1}a^{k+1})^2 \equiv a\pmod{p},$ and again we have found an explicit solution of the congruence $x^2\equiv a \pmod{p}$.

Unfortunately, finding square roots modulo $p$ is not always so straightforward.