Quadratic congruences with prime modulus

Ch1ronTL34

The question is:

Show that if p == 1 mod 4, then (a/p) = (-a/p).
(Note that == means congruent).

I know that if X^2==a mod p (p is a prime) is solvable then a is a quadratic residue of p.

For an example, I let p = 5 since 5==1 mod 4. Then, I let X = 2 and 4 just to check the equation. So:

2^2==-1 mod 5...........a=-1 is quadratic residue.
4^2==1 mod 5............a=1 is quadratic residue.

I know that the legendre symbol (a/p) is 1 if a is a quadratic residue mod p and -1 if a is a quadratic non-residue.

From my example, (-1/5)=1 and (1/5)=1, so I have found an example that shows (a/p) = (-a/p) but I'm having trouble proving it in general.

Thanks!

shmoe

Do you know anything about (-1/p)? Have you seen Euler's criteron?

AKG

p = 1 (mod 4) implies (-1/p) = 1.

Ch1ronTL34

No shmoe, I don't know anything about (-1/p) and I just did some research on Euler's criterion:

if a is quadratic residue modulo p (i.e. there exists a number k such that k^2 ≡ a (mod p)), then

a^(p − 1)/2 ≡ 1 (mod p)
and if a is not a quadratic residue modulo p then

a^(p − 1)/2 ≡ −1 (mod p).

I'm not really seeing the connection of why this helps....thanks again

shmoe

If you are happy using Euler's criterion, how do

a^(p-1)/2 mod p

and

(-a)^(p-1)/2 mod p

compare when p=1 mod 4?

Also, by looking at (-1)^(p-1)/2 mod p, you can prove what AKG posted with Euler's.

If this is for a class, you should try to prove it using methods you've covered though. What do you know so far about the legendre symbol?

Ch1ronTL34

This is for a class but he didn't teach us ANYTHING about the legendre symbol. I'm guessing that 1 mod 4 implies (-1/p)=1 is critical but i still don't really understand.

I took shmoe's advice and found that, when p==1 mod 4
a^(p-1)/2 mod 5 equals (-a)^(p-1)/2 mod 5

shmoe

Oi, do you at least have a text you're expected to have access to?

5 is just one specific example of such a prime, but we can go with this a little bit. More important is what happens in the exponent, when p is 5, (p-1)/2=2. and you have:

a^(p-1)/2 =a^2 mod 5

and

(-a)^(p-1)/2 =(-a)^2=(-1)^2 * a^2 =a^2 mod 5

So you'd have

a^(p-1)/2 = (-a)^(p-1)/2 mod 5

and therefore (a/p)=(-a/p)

What was important here is the (-1)^(p-1)/2 part. It was 1 when p=5 above. What can you say about (-1)^(p-1)/2 when p=1 mod 4?


This is really asking about (-1/p). It comes in here because (-a/p)=(-1/p)*(a/p). More generally you'd have (a*b/p)=(a/p)*(b/p).

Ch1ronTL34

Yes shmoe, I do have a textbook...."Elementary Theory of Numbers" by William J. LeVeque. Unlike most mathbooks, this one is about 100 pages and very small....though its size has proven to be misleading...ANYWAYS:

When p==1 mod 4, (-1)^(p-1)/2 will be an even number because p will be odd (p=4d+1 for some d) and (p-1)/2 will be an even number...(-1)^even number is 1.

shmoe

LeVeque is a nice little book. It works in the ties with abstract algebra well.

Exactly. If p=3 mod 4, (p-1)/2 would have been odd, so you'd end up with -1, and you hopefully see (-1/p) is completely determined by p mod 4.

Back to your problem, you should now be able to show

(-a)^(p-1)/2 = a^(p-1)/2 mod p

when p=1 mod 4, by just pulling out the -1 from the left hand side like I did above. That's pretty much it.

Ch1ronTL34

Alright I think I get it now. Thanks so much for the help shmoe!