Asked by JoSCo 21 months ago

Details:

Show that x^2 is congruent to (p - x)^2 (modulus p) and these are the only congruences among 1^2, 2^2, 3^2, ..., (p - 1)^2. (A congruence mod some number means that the two congruent numbers have the same remainder when divided by the modulus.)


1
 Forward to friends
 Discuss this question (13 comments) why can't I answer? Report abuse

av-answers (2)
(13)
 
Show all details, Hide all details

"Here you go!"

 by Paradise.t on May 02 2008 (21 months ago)
 Best Answer
Official Rating

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.

Paradise.t's Recommendations
Product Image
Amazon List Price: $16.00
Used from: $6.27
Average Customer Rating: 4.5 out of 5 (based on 79 reviews)
Like this Answer?

"I can't think of any justification to assist you on your homework"

 by ElBanditoRoso on Apr 29 2008 (21 months ago)
Official Rating

But the question is simple if you take the square of the second polynomial and divide
Like this Answer?




Ask a question of your own:


 

Latest post on this question's discussion board:

These are really helpful answers! Thank you so much. Also for the book suggestion.
Read more & discuss (13 comments)