The Student Room Group

Modular arithmetic proof (check please?)

A simple Q from courant's book:
Question as stated in the book:
We have seen that x2(px)2(modp)x^{2}\equiv (p-x)^{2}(mod p) . Show that these are the only congruences among the numbers 12,22,32,...,(p1)21^{2},2^{2},3^{2},...,(p-1)^{2}.

The question one its own I found quite ambigious, as I think p must be a prime, which is implied by the previous pages but not explicitly stated. So, my (hopefully equivalant) interpretation is: considering p is a prime, show that no other number pairs from the set 12,22,32,...,(p1)2{1^{2},2^{2},3^{2},...,(p-1)^{2}} are congruent module p other than x2(px)2(modp)x^{2}\equiv (p-x)^{2}(mod p) .

Proof:

Assume x2(py)2(modp)x^{2}\equiv (p-y)^{2}(mod p) , for 1xp11\leq x\leq p-1, and 1pyp11yp11\leq p-y\leq p-1\Rightarrow 1\leq y\leq p-1, and x+ypx+y\neq p

Then, we have x2(py)2(modp)(x+py)(xp+y)0(modp)pxyx^{2}\equiv (p-y)^{2}(mod p)\Rightarrow (x+p-y)(x-p+y)\equiv 0(mod p)\Rightarrow p|x-y or px+yp|x+y as p is a prime.

We know x-y is less that p , so p divides this only if x=y, gives the congruent pair stated in the question.
Also, x+y is positve, less than 2p and not equal to p, so p can not clearly divide this.

Hence no other congruent pair exist. Question was quite easy, so hopefully no mistakes.
Original post by twig
...


Can't see anything wrong with that.

You do need p as prime; e.g. 1232  (mod  8)1^2 \equiv3^2 \;(mod \;8)
Reply 2
Original post by ghostwalker
Can't see anything wrong with that.

You do need p as prime; e.g. 1232  (mod  8)1^2 \equiv3^2 \;(mod \;8)


Thank you.

Yeah, my proof relied on this, and also notation of mod p suggested as much.

Quick Reply

Latest