# Homework Help: Congruences of quadratic residues

1. Aug 9, 2010

### 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.

1. The problem statement, all variables and given/known data
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}$$

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

3. The attempt at a solution
No idea..

babak

2. Aug 9, 2010

### 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

3. Aug 10, 2010

### Baba-k

Hi Petek,

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

cheers
babak

4. Aug 22, 2010

### 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

5. Aug 22, 2010

### Petek

Looks good!

6. Aug 22, 2010

### Dick

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?

Last edited: Aug 22, 2010
7. Aug 23, 2010

### Baba-k

Hi Dick,

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

8. Aug 23, 2010

### epenguin

is it not fairly obvious to you that

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

since p is a factor of that bit?

9. Aug 23, 2010

### Dick

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?

10. Aug 30, 2010

### 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

11. Aug 31, 2010

### Dick

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.

12. Aug 31, 2010

### Baba-k

Riteo dont worry, was just confusing my self hehe.