Problem involving existence of solutions for x^2 = a (mod p)

[demonelite123]

If p is prime and (a, p) = 1, show that $x^2 \cong a (mod p)$ has solutions if $a^{\frac{p-1}{2}} \cong 1 (mod p)$ and does not have solutions if $a^{\frac{p-1}{2}} \cong -1 (mod p)$.

So because of Euler's theorem i know that $a^{p-1} \cong 1 (mod p)$ and from the hypothesis $a^{\frac{p-1}{2}} \cong 1 (mod p)$. I am first trying to show that $x^2 \cong a (mod p)$ has solutions. I've tried things such as multiplying both sides of the first 2 congruences by a, $a^{p} \cong a (mod p)$ and $aa^{\frac{p-1}{2}} \cong a (mod p)$ so $aa^{\frac{p-1}{2}} \cong a^p (mod p)$. and multiplying by the inverse of $a^{\frac{p-1}{2}}$ on both sides i get $a \cong a^{\frac{p-1}{2}} (mod p)$. but i can't seem to find such an x since i don't think i can split $a^{\frac{p-1}{2}}$ into something of the form $x^2$. i have been trying to manipulate the 2 congruences but i can't seem to find a way to show that $x^2 \cong a (mod p)$ has a solution. can someone offer a hint or two in the right direction? thanks!

 

[dodo]

First, the question probably says that p is an odd prime; with p=2 the question has not much sense, since $1 \equiv -1 \pmod 2$. Then the exponent (p-1)/2 is always an integer, by the way.

When looking for a solution "x", you consider the numbers 1, 2,..., p-1, because 0 is not going to be a solution of your equation: "a" is non-zero if (a,p)=1. Now, play with a small numerical example, p=7 and a=3, to get some idea. Play with these numbers to see which multiply to give 3: 1x3, 2x5, 4x6 all give 3 modulo 7. (So none repeats: it's always one number times a different number, so your congruence has no solutions in this case.) At this point, go back to your book and review the proof of Wilson's Theorem... you may find it illustrative.

P.S.: By the way, if something (in this case, 5) multiplies 2 in order to give 3 (mod 7), then nothing else will multiply 2 to give 3 (mod 7). It's not hard to check that the congruence $by \equiv a \pmod p$, for some given "b" (and "a" and "p") has a unique solution (when "a" and "b" are non-zero, that is).

P.P.S: This is a known statement, so this line of proof is not mine -- I cheated and saw the proof so that you don't have to, and can have a shot at trying yourself.

 

[demonelite123]

i've reviewed the proof of Wilson's theorem but i don't know how that helps me out. the proof uses the fact that $x^2 \equiv 1 (mod p)$ has soutions $x \equiv 1 (mod p)$ or $x \equiv -1 (mod p)$. but i can't figure out how to apply that to $x^2 \equiv a (mod p)$.

i've also tried taking $x^2 \equiv a (mod p)$ and raising both sides to the power of (p-1)/2. then i get $x^{p-1} \equiv a^\frac{p-1}{2} (mod p)$. in the case where $a^\frac{p-1}{2} \equiv 1 (mod p)$ i can see that $x^{p-1} \equiv 1 (mod p)$ which is definitely a true statement given that (x, p) = 1. On the other hand, when $a^\frac{p-1}{2} \equiv -1 (mod p)$ i can see that $x^{p-1} \equiv -1 (mod p)$ and if (x, p) = 1 then this cannot be true for any x so there are no solutions in this case. I'm not sure if this argument is valid or not but its all i could think up of as of now. if this is wrong i would greatly appreciate some further assistance on this problem.

 

[dodo]

Perhaps I had in mind an analogy too remote, but in Wilson's proof there is a pairing of the numbers from 1 to p-1 which is reminiscent (not exact) of what a possible proof for the statement here would be. (And Wilson's result is involved at some point after this pairing. Think: if 1x3, 2x5, 4x6, all give 3 modulo 7, how do you obtain the factorial of 6? And what power of 3 is that?) Leaving that aside for a moment, let me go to the work you did.

I think it's only half there. You need to prove two statements: one for the situation where the power of "a" is 1, and one for when it is -1. I think the contradiction you find for the second part is OK, but not finding a contradiction in the first part is not a proof. Some rephrasing could also be used: raising the statement $x^2 \equiv a \pmod p$ to the power of (p-1)/2 is fine... as long as your reader is remainded that, at this stage, we don't know if an "x" exists at all. The assumptions are the statements about 1 and -1, on each case; the existence of a solution to the quadratic congruence is the place to arrive, and you'd only assume the latter (or its new version after raising to the (p-1)/2 power) when the intention is to find a contradiction.

Back to my original suggestion, in my defense :) I should say that the "known" statement I mentioned happens to consist actually of "if-and-only-if" propositions, thus stronger than the one you set to prove. If you just need to deliver a proof of the milder statement as given, maybe (I don't know) a complete proof (more than half of it) can be found on the direction you are attempting; I can't think of one right now, but that may be me.

I hope I'm not being too sadistic :), I just had the impression that you wanted to do this yourself. Also, please let me know if I missed something in your reasoning about the first part of the proof.

 

[ramsey2879]

i've reviewed the proof of Wilson's theorem but i don't know how that helps me out. the proof uses the fact that $x^2 \equiv 1 (mod p)$ has soutions $x \equiv 1 (mod p)$ or $x \equiv -1 (mod p)$. but i can't figure out how to apply that to $x^2 \equiv a (mod p)$.

i've also tried taking $x^2 \equiv a (mod p)$ and raising both sides to the power of (p-1)/2. then i get $x^{p-1} \equiv a^\frac{p-1}{2} (mod p)$. in the case where $a^\frac{p-1}{2} \equiv 1 (mod p)$ i can see that $x^{p-1} \equiv 1 (mod p)$ which is definitely a true statement given that (x, p) = 1. On the other hand, when $a^\frac{p-1}{2} \equiv -1 (mod p)$ i can see that $x^{p-1} \equiv -1 (mod p)$ and if (x, p) = 1 then this cannot be true for any x so there are no solutions in this case. I'm not sure if this argument is valid or not but its all i could think up of as of now. if this is wrong i would greatly appreciate some further assistance on this problem.

You might consider that the complete set of residues equals {r^n} with r being a primitive root of p and 0 < n < p. Then the set with n even will be the square residues while the set with n odd will be the non-square residues. n(p-1)/2 will then be a multiple of p-1 when n is even but will only be a multiple of (p-1)/2 when n is odd.

 

[pedja]

http://en.wikipedia.org/wiki/Proth's_theorem