Thread: Let p be a prime...

1. Let p be a prime...

Let p be a prime. Let r1, r2, ..., rp-1 be the integers 1, 2, ..., p-1 in some order. Prove that some two of the numbers

1*r1, 2*r2, ..., (p-1)*rp-1

must be congruent modulo p.
[Hint: If not, think of their product modulo p.]

(The 1, 2, and p-1 when following an r are supposed to be subscript. I can't seem to figure out how to make them and keep them that way.)

2. Originally Posted by NikoBellic
Let p be a prime. Let r1, r2, ..., rp-1 be the integers 1, 2, ..., p-1 in some order. Prove that some two of the numbers

1*r1, 2*r2, ..., (p-1)*rp-1

must be congruent modulo p.
[Hint: If not, think of their product modulo p.]

(The 1, 2, and p-1 when following an r are supposed to be subscript. I can't seem to figure out how to make them and keep them that way.)

Well, let's check the product! : $r_1\cdot 2r_2\cdot\ldots\cdot(p-1)r_{p-1}$ ; but by Wilson' Theorem, if all these elements are different modulo p then their product is the same as

$1\cdot 2\cdot\ldots\cdot(p-1)=-1\!\!\!\pmod p$ . On the other hand we can write $1r_1\cdot 2r_2\cdot\ldots\cdot(p-1)r_{p-1}=(1\cdot2\cdot\ldots\cdot(p-1))(1\cdot2\cdot\ldots\cdot (p-1))=(-1)\cdot(-1)=1\!\!\!\pmod p$ ...contradiction.

Tonio