Product of quadratic nonresidues is a residue

[Broccoli21]

Homework Statement

Prove that if p is prime, then if A is a quadratic nonresidue mod p and B is also a quadratic nonresidue mod p, then AB is a quadratic residue mod p.

Homework Equations

A is a nonresidue means A = x^2 (mod p) has no solutions

The Attempt at a Solution

I already proved that product of two residues is a residue, and that a residue and a nonresidue make a nonresidue. Also it's easy to prove by contradiction that 1/A (which always exists because p is prime) is a residue iff A is a residue.

Now as for the given question, I have actually solved it using group theory, but the class requires a proof from elementary principles. We have not covered the legendre symbol either. My proof is this:

the integers Z_p={0...p-1} form a cyclic group under multiplication, and thus have a generator g. So any integer in Z_p can be written as a power of g, so the residues are even powers and the nonresidues are odd powers. So A=g^odd and B=g^odd so AB=g^odd+odd=g^even so AB is a residue.

I can't seem to extend this to an elementary proof (using congruences and whatnot) though, and can't even see a way to start.

Thanks in advance!

 

[micromass]

the integers Z_p={0...p-1} form a cyclic group under multiplication

This is not true.

[itex]\mathbb{Z}_p\setminus \{0\}[/itex] is a cyclic group though.

What can you use?? Can you use Fermat's little theorem?

 

[Broccoli21]

This is not true.

[itex]\mathbb{Z}_p\setminus \{0\}[/itex] is a cyclic group though.

What can you use?? Can you use Fermat's little theorem?

Oh thanks for catching that. Yeah I suppose that doesn't work. Using fermat's little theorem, we know that:

a = a^p (mod p)
b = b^p (mod p)
ab = (ab)^p (mod p)

but here, I can't really see how to proceed. How do I use the fact they a and b are non-residues?

If we let q=(p-1)/2, we also get an integer such that

(ab)^2q = 1 (mod p)

but this ultimately seems to get going nowhere :|
sorry that I can't seem to see where to apply the given conditions

 

[micromass]

Do you know that a is a quadratic residue iff [itex]a^{(p-1)/2}=1[/itex] (mod p) and -1 otherwise??

 

[Broccoli21]

I am not aware of that theorem. I managed to prove that if a is a residue, then indeed:
(everything below is mod p)
a = x^2
hence:
a^(p-1)/2 = x^p-1 = 1
to prove the opposite direction, assume that a^(p-1)/2 = 1. Then:
I can't seem to prove that in this case, a is a residue. However I did that, then because we can factor fermat's little theorem:
0 = (a^(p-1)/2 -1)(a^(p-1)/2 +1)
, the only two possible values for a^(p-1)/2 are +1 and -1 so I would be done, and this statement would imply the result of the original problem.

However I don't know how to prove that a^(p-1)/2 = 1 implies that a is a residue. Thanks for the help so far, by the way!

 

[micromass]

Hmmm, I see no other proof than using that there exists an element g such that all integers x with gcd(x,p)=1 can be written as [itex]g^n=x[/itex] (mod p) for a certain n. But this is not a basic result.

 

[Broccoli21]

I think I might have solved it. Can you check if this works?
suppose a is a quadratic nonresidue
We know in general that if:
cb=db
then
b(c−d)=0
so c=d.

Thus for b∈{1,...,p−1}, {b,2b,...,(p−1)b} is {1,...,p−1} rearranged modulo p, and for all b∈{1,...,p−1}, there is exactly one c∈{1,...,p−1} such that cb=a (mod p of course). We also note that if c=b, then c=1 or c=p-1 so since a is not a residue, c=/=b.

Thus we partition the set {1,...,p−1} into pairs with that property. Now notice that the product:

(1)(2)...(p-1)=(p-1)! contains all of these pairs, of which there are (p-1)/2.
So
(p-1)! = a^(p-1)/2

but another way to look at (p-1)! is that we can group all the numbers in a similar fashion as before, but now with cb=1. But remember that c=b iff c=1 or c=p-1. So ignore those and compute the product:

(2)(3)...(p-2)=(p-2)! = 1

now multiply by p-1:

(p-1)! = p-1 = -1.

so if we go back to equation 1), we see

a^(p-1)/2 = -1, the desired result for nonresidues.

Does this work?

 

[micromass]

That seems correct. Very, very nice solution!

 

[Broccoli21]

Thanks Micromass!