"Show that x^2 is congruent to (p - x)^2 (modulus p) and these are the only congruences among 1^2, 2^2, ..., (p - 1)^2"

Assume x^2 and y^2 are congruence mod. p. By definition their difference should be divisible by p.

There fore x^2-y^2 is divisible by p. Hence p divides (x^2-y^2). We can now factorize x^2-y^2.

x^2-y^2 = (x-y) * (x+y)

We know that if p divides the product of two numbers p divides one of them, since p is a prime. Therefore:

p divides either x-y or x+y

Now assume 0< y <  x < p

Therefore we have 0 < x-y < p and  0 < x+y < 2p

Since no number that is divisible by p can be between zero and p , x-y cannot be divisible by p. Therefore x+y is divisible by p.

Since x+y is between zero and 2p and the only number divisible by p in this interval is p we should have:

x+y = p

Hence y = p-x, which proves what you want. I.e. x^2 is congruent to y^2 only when y = p-x (provided x and y are between 1 and p-1)

Also if y = p-x then by the same argument x^2 - y^2 is divisible by p. Because you can factorize that as we did above and get a multiple of p.

We are done with the solution of this problem here.

------------------------------------------------------------

One interesting observation is that (p-x)^2 and x^2 ARE even congruent as polynomials. The reason is that if you expand (p-x)^2 you get:

(p-x)^2 = p^2 + x^2 - 2*p*x Now the first and last terms are divisible by p and hence are zero mod. p.

-----------------------------------------------------------

Another interesting point that I would like to mention here is that two polynomials can be NOT congruent mod a prime p while they ARE congruent for any value of x. That is a very important and interesting observation. An example of such polynomials would be x^p and x.

As you know for any integer x we have x^p is congruent to x  mod. p but as polynomials they are NOT congruent. By definition two polynomials are congruent if their corresponding coefficients are congruent, but the coefficient of x in one of them is 1 while in the other one is zero. So they are not congruent.

Congruent polynomials are of very importance. You can more or less develop the factorization that we have for real polynomials when we are dealing with polynomials with integer coefficients in mod. p. (p is a prime)

As an example look at the polynomial x^p-x. This polynomial is zero mod. p for x= 0, 1, ..., p-1

You can then factorize this polynomial in mod. p. Therefore we have:

x^p-x = x (x-1) (x-2) ... (x-(p-1)) (mod. p)

This simple fact can give us interesting results. For example by looking at the coefficient of x we have:

(p-1)! = -1 (mod. p)

Looking at other coefficients also give us interesting results.

But the question is simple if you take the square of the second polynomial and divide