What are the Quadratic Residues Modulo p?

[knowLittle]

Homework Statement

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.

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.

 

[Dick]

Homework Statement

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.

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.

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.

 

[knowLittle]

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.

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)?

 

[haruspex]

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?

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.

 

[Dick]

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)?

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.

 

[knowLittle]

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.

Thank you!