Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Do you know that $\left(\frac a p\right)\equiv a^{\frac{p-1}{2}}\pmod p$? –  Thomas Andrews Jun 24 '12 at 16:11
    
Yes, I do know that. –  Jozef Jun 24 '12 at 16:13
    
can just use the equation $x^2 \equiv 1(\bmod p)$ for showing that first claim? –  Jozef Jun 24 '12 at 16:17

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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