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]

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!

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

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

multiplicative group \left(Z/pZ\right)^{*} is a divisor of 2k + 1 (please do note that always (2k+1)|(p-1) )...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, p-1=5+8\cdot k -1 = 4(2k+1)\Longrightarrow , and since it is always true that y\in\left(Z/pZ\right)^* is a quad. res. \,\Longleftrightarrow 1=y^{\frac{p-1}{2}} , then

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

Hope the above helps.

DonAntonio

 

[squire636]

Got it, thanks so much!