1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Product of quadratic nonresidues is a residue

  1. Apr 10, 2012 #1
    1. The problem statement, all variables and given/known data
    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.

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

    3. 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. :frown:

    Thanks in advance!
  2. jcsd
  3. Apr 10, 2012 #2
    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?
  4. Apr 10, 2012 #3
    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
  5. Apr 10, 2012 #4
    Do you know that a is a quadratic residue iff [itex]a^{(p-1)/2}=1[/itex] (mod p) and -1 otherwise??
  6. Apr 10, 2012 #5
    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
    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!
  7. Apr 10, 2012 #6
    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.
  8. Apr 10, 2012 #7
    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:
    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.
    (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?
  9. Apr 10, 2012 #8
    That seems correct. Very, very nice solution!!
  10. Apr 10, 2012 #9
    Thanks Micromass!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook