- #1

- 219

- 0

## Main Question or Discussion Point

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

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

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