Where does p = 5 (mod 8) solve x^2 = a?

squire636

The problem is actually slightly simpler than that, but I couldn't fit it all into the topic title.

Let p be a prime satisfying p = 5 (mod 8) and suppose that 'a' is a quadratic residue modulo p. I need to show that one of the values:

x = a^(p+3)/8 or x = 2a*(4a)^(p-5)/8

is a solution to the congruence x^2 = a (mod p).


I really have no idea how to even start this. If it was just a single case, I think I would be able to make some progress, but since I have to prove that one or the other works (depending on the situation), I'm totally lost. Any help is appreciated. Thanks!

dodo

Hi, squire,
if I understood the question correctly, note that it is *not* about finding values of x and a that satisfy one of the solutions together with x^2≡a (actually, x≡a≡0 will satisfy both solutions). It is about choosing the one of the two solutions that makes x^2≡a always true for *all* values of x,a (and p) that satisfy the solution. So you're looking for a single counterexample that invalidates one of the solutions. You may try substituting x^2 for a on both proposed solutions, and then seeing if some value of x does not work for some p.

Also, I don't think the question is about one of the expressions being "the one and only form" of the solution of x^2≡a. It only asks for one of the expressions to be *a* possible solution (there may be other forms that can be solutions -- but the *other* expression, the one of the two that you don't choose, must clearly fail).

squire636

Well parts (b) and (c) of this question ask me to find a numerical solution for a particular case. For (b), one of the options provides a correct solution, but for (c) the other option provides a correct solution. So I think each one works for different cases. I'm not sure if what I said was clear, so let me know if you need me to clarify.

morphism

Hint: Because a is a quad residue mod p, Euler's criterion tells us that ##a^{\frac{p-1}{2}} \equiv 1 \pmod{p}##.

DonAntonio

Let's see if I got this right. We operate all the time modulo p, and let [itex]p=5+8\cdot k[/itex] be a prime number and we assume [itex]a\neq 0[/itex]:

suppose [itex]x=a^{\frac{p+3}{8}}=a^{k+1}\Longrightarrow a=x^2=a^{2(k+1)}\Longrightarrow a^{2k+1}=1\Longrightarrow \,[/itex] the order of a in the

multiplicative group [itex]\left(Z/pZ\right)^{*}[/itex] is a divisor of 2k + 1 (please do note that always [itex](2k+1)|(p-1)[/itex] )....and so we suspect that when the order of a

is greater than 2k + 1 then it is the second formula that works (since then the first one cannot possibly work, of course).

But, in fact, [itex]p-1=5+8\cdot k -1 = 4(2k+1)\Longrightarrow[/itex] , and since it is always true that [itex]y\in\left(Z/pZ\right)^*[/itex] is a quad. res. [itex] \,\Longleftrightarrow 1=y^{\frac{p-1}{2}}[/itex] , then

[itex]1=a^{\frac{p-1}{2}}=a^{2(2k+1)}\Longrightarrow\,\, [/itex] the order of a is [itex]2(2k+1)[/itex] as expected, since it cannot be [itex]4(2k + 1)=p-1\,\,[/itex] (why?).

Hope the above helps.

DonAntonio

squire636

Got it, thanks so much!