If q is a prime and q is congruent with 1(mod 4), show there is an integer a such that a^2is congruent with -1 (mod p).
The hint provided is to show that there's an integer x of order 4 modulo p.
I'm really stuck and I have no idea what to do. I assume the hint means to show x^2 is congruent with 1 (mod p)?
Thanks for your help.
The hint provided is to show that there's an integer x of order 4 modulo p.
I'm really stuck and I have no idea what to do. I assume the hint means to show x^2 is congruent with 1 (mod p)?
Thanks for your help.
-
Assuming that p (not q) is the prime congruent to 1 (mod 4):
------------------------
Note that x having order 4 mod p implies that x^2 = -1 (mod p).
Why?
Since x^4 = 1 (mod p), we have x^4 - 1 = 0 (mod p)
==> (x^2 - 1)(x^2 + 1) = 0 (mod p)
==> x^2 - 1 = 0 (mod p) or x^2 + 1 = 0 (mod p).
==> x^2 = -1 or 1 (mod p).
x^2 = 1 (mod p) is impossible, because that would imply that the order of x mod p equals 2; which contradicts the order of x equaling 4. So, x^2 = -1 (mod p).
----------
Now, x^2 = -1 (mod p) is solvable when p = 1 (mod 4), because
(-1/p) = (-1)^((p-1)/2) = 1, via Legendre (quadratic residue) symbol.
I hope this helps!
------------------------
Note that x having order 4 mod p implies that x^2 = -1 (mod p).
Why?
Since x^4 = 1 (mod p), we have x^4 - 1 = 0 (mod p)
==> (x^2 - 1)(x^2 + 1) = 0 (mod p)
==> x^2 - 1 = 0 (mod p) or x^2 + 1 = 0 (mod p).
==> x^2 = -1 or 1 (mod p).
x^2 = 1 (mod p) is impossible, because that would imply that the order of x mod p equals 2; which contradicts the order of x equaling 4. So, x^2 = -1 (mod p).
----------
Now, x^2 = -1 (mod p) is solvable when p = 1 (mod 4), because
(-1/p) = (-1)^((p-1)/2) = 1, via Legendre (quadratic residue) symbol.
I hope this helps!