Congruences of quadratic residues

[Baba-k]

Hi,

I'm slowly reading through the book What is Mathematics which asks the following question at the end of its quadratic residues section. I'm not sure how to begin it really, so any hints/suggestions would be greatly appreciated.

Homework Statement

We have seen that $$x^{2} \equiv (p - x)^{2} \pmod p$$. Where p is a prime > 2 and x is not divisible by p
Show that these are the only congruences among the numbers $$1^{2}, 2^{2}, 3^{2},...,(p-1)^{2}$$

Homework Equations

$$(p-x)^{2} = p^{2} - 2px + x^{2}\equiv x^{2} \pmod p$$

The Attempt at a Solution

No idea..

thanks in advance,
babak

 

[Petek]

I think we have to define what the author means by "the only congruences among the numbers $1^{2}, 2^{2}, 3^{2},...,(p-1)^{2}$." I'd say that he means something like:

If a,b $\in$ {1, 2, ..., p-1}, a $\neq$ b and $a^2 \equiv b^2 (mod p)$, then a = p-b.

Can you prove that?

Petek

 

[Baba-k]

Hi Petek,

Thanks the response. I'm not sure how atm but will give it ago hehe

cheers
babak

 

[Baba-k]

Hi Petek,

Heres what I've come up with, what do you think ?

$$a^{2} \equiv b^{2} \pmod p$$
$$a^{2} - b^{2}\equiv 0 \pmod p$$
$$(a-b)(a+b)\equiv 0 \pmod p$$

$$(a-b)\equiv 0 \pmod p \texttt{ or } (a+b)\equiv 0 \pmod p$$
$$a+b=p \texttt{ or } a-b=p$$

$$a=p-b \texttt{ as } a\in \left \{ 1, 2,...,p-1 \right \} \texttt{ hence } a<p$$

thanks alot,
babak

 

[Petek]

Looks good!

 

[Dick]

Hi Petek,

Heres what I've come up with, what do you think ?

$$a^{2} \equiv b^{2} \pmod p$$
$$a^{2} - b^{2}\equiv 0 \pmod p$$
$$(a-b)(a+b)\equiv 0 \pmod p$$

$$(a-b)\equiv 0 \pmod p \texttt{ or } (a+b)\equiv 0 \pmod p$$
$$a+b=p \texttt{ or } a-b=p$$

$$a=p-b \texttt{ as } a\in \left \{ 1, 2,...,p-1 \right \} \texttt{ hence } a<p$$

thanks alot,
babak

That IS a good start. But it's a little sloppy. i) Where did you use that p is prime? ii) If a and b are in {1...p-1} it's pretty unlikely that a-b=p, don't you think? Can you elaborate a little?

 

[Baba-k]

Hi Dick,

Thanks for your comments.

i) The product $$(a-b)(a+b)\equiv 0 \pmod p$$ is divisible by the prime p only if one of the factors is, so either $$a-b\equiv 0$$ or $$a+b\equiv 0 \pmod p$$ must be divisible by p.

ii) I chose $$a+b=p$$ as $$a \in \left \{1,..,p-1 \right \}$$ so will always be < p but with $$a-b=p, a=p+b$$ which is >p, which isn't possible.

What do you think ?

cheers
babak

 

[epenguin]

In your middle term here

Homework Equations

$$(p-x)^{2} = p^{2} - 2px + x^{2}\equiv x^{2} \pmod p$$

is it not fairly obvious to you that

p² - 2px = 0 (mod p) (identity)

since p is a factor of that bit?

 

[Dick]

Hi Dick,

Thanks for your comments.

i) The product $$(a-b)(a+b)\equiv 0 \pmod p$$ is divisible by the prime p only if one of the factors is, so either $$a-b\equiv 0$$ or $$a+b\equiv 0 \pmod p$$ must be divisible by p.

ii) I chose $$a+b=p$$ as $$a \in \left \{1,..,p-1 \right \}$$ so will always be < p but with $$a-b=p, a=p+b$$ which is >p, which isn't possible.

What do you think ?

cheers
babak

i) is right on. ii) is still a little funny. If a number is divisible by p then it must have the form k*p where k is a integer, right? If a and b are in {1...p-1} and a+b is divisible by p then a+b=p, since it can't be 0 and it can't be as large as 2*p. And if a-b is divisible by p shouldn't a-b=0?

 

[Baba-k]

Hi,

Okay thanks, think I see what you're saying. Is it enough to say..

since $$(a+b)(a-b)\equiv 0 \pmod p$$ then
$$a+b=np$$ or $$a-b=kp$$ where $$a, b \in \left \{ 1, ..., p-1 \right \}$$
if $$a-b=kp$$ then $$a-b$$ will always be < p and hence k is 0. While $$0 < a+b < 2p$$. Hence n is 1 as we've already said that a-b=0.

Pretty much just re-written what you said before I guess hehe. Am not too sure about the logic for getting to n=1 though..

cheers!
babak

 

[Dick]

Hi,

Okay thanks, think I see what you're saying. Is it enough to say..

since $$(a+b)(a-b)\equiv 0 \pmod p$$ then
$$a+b=np$$ or $$a-b=kp$$ where $$a, b \in \left \{ 1, ..., p-1 \right \}$$
if $$a-b=kp$$ then $$a-b$$ will always be < p and hence k is 0. While $$0 < a+b < 2p$$. Hence n is 1 as we've already said that a-b=0.

Pretty much just re-written what you said before I guess hehe. Am not too sure about the logic for getting to n=1 though..

cheers!
babak

a+b is a multiple of p. Since it's also between 0 and 2p that means it's equal to p, right? I'm not sure what you are not sure about.

 

[Baba-k]

Riteo don't worry, was just confusing my self hehe.

thanks for all your help!