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: Quadratic Residues Modulo p

  1. Jan 17, 2013 #1
    1. The problem statement, all variables and given/known data
    Let p be an odd prime. A number ##a\in \mathbb{Z} _{p}^{\ast }## is a quadratic residue if the equation ##x^{2}=a\left( \mod p\right)## has a solution for the unknown x.

    a. Show that there are exactly (p-1)/2 = quadratic residues, modulo p.

    3. The attempt at a solution
    I have access to the "proof", but I have some questions that need clarification:

    Suppose that b1 and b2 are numbers between 1 and (p - 1)/2 , and suppose that
    ##b_{1}^{2}\equiv b_{2}^{2}(mod p) ## We want to show that b1 = b2. The fact that ##b_{1}^{2}\equiv b_{2}^{2}(modp)## means that p divides ##\left( b_{1}^{2}-b_{2}^{2}\right) =\left( b_{1}-b_{2}\right) \left( b_{1}+b_{2}\right)##
    OR that ##\left( b_{1}^{2}-b_{2}^{2}\right) =\left( b_{1}-b_{2}\right) \left( b_{1}+b_{2}\right)## = p. k, where k is an integer.

    However, b1+b2 is between 2 and p-1, so it can't be divisible by p.
    Thus, p must divide b1-b2. But, |b1-b2| < (p-1)/2, so the only way for b1-b2 to be divisible by p is to have b1=b2.
    QUESTION: p represents an odd prime. Primes can only be divisible by 1 or itself.
    By stating that |b1-b2|< (p-1)/2 and that b1=b2, they try to explain that the b1 and b2 is not 0, but it's just the same number. Does it mean that b1=b2 has to be 1?
    Or, is it saying that it's impossible that p divides b1^(2) - b2^(2) given b1≠b2 ?

    This shows that ##1^{2},2^{2},\ldots ,\left( \dfrac {p-1} {2}\right) ^{2}## are all different modulo p, so there are exactly (p-1) /2 quadratic residues modulo p.

    Thank you.
  2. jcsd
  3. Jan 17, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    They are trying to argue that b1 must equal b2. b1-b2=1 doesn't work. p has to divide b1-b2, not b1-b2 divide p.
  4. Jan 17, 2013 #3
    I didn't say that b1-b2=1, I meant that b1=b2=1.
    So, supposedly since p|(b1-b2); b1-b2= kp, where k is an integer. Are they saying that it's impossible p | (b1-b2) , unless b1=b2 or in other words that p|0 or 0= pk, where k is any integer and in this case k=0?
    Or are they saying that it's impossible to have two different numbers b1, b2 such that p| (b1-b2)?
  5. Jan 17, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The argument is that if |c| < p and p divides c then c must be 0. Substituting c = b1-b2 shows p does not divide b1-b2 unless b1=b2, and substituting c = b1+b2 shows p does not divide that either.
  6. Jan 17, 2013 #5


    User Avatar
    Science Advisor
    Homework Helper

    Yes, it's impossible because |b1-b2|<(p-1)/2. The only way it can be divisible by p is if b1-b2=0 so b1=b2.
  7. Jan 17, 2013 #6
    Thank you!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook