- #1
Broccoli21
- 80
- 1
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!