1. ## complete residue modulo

Greetings! The problem: if r1, r2, r3, ..., rp and r'1, r'2, r'3, ... , r'p are any two complete residue systems modulo a prime p > 2, prove that the set r1 * r'1, r2 * r'2, r3 * r'3, ... , rp * r'p cannot be a complete residue system modulo p.

2. Greetings! The solution : by Wilson's theorem, $\displaystyle r_1\hdots r_n \equiv r'_1\hdots r'_n \equiv -1 \mod p$.

But $\displaystyle r_1r'_1 \hdots r_nr'_n \equiv (-1)^2 \equiv 1 \mod p$.

So $\displaystyle r_1r'_1, \hdots, r_nr'_n$ cannot be a complete system of residues.

3. How do you know that (p-1)! is congruent or equal to r1 * r2 * ... * rp
and congruent to r'1 * r'2 * ... * r'p?

4. Oh sorry I was thinking reduced system. I hadn't had my coffee yet . But the heart of the solution is there.

One of the $\displaystyle r$'s is $\displaystyle \equiv 0$ (say $\displaystyle r_i$) and similarily for one of the $\displaystyle r'$ 's (say $\displaystyle r'_j$). So if we want to avoid having two of the $\displaystyle r\: r'$ 's congruent to 0 - because then we obviously couldn't get a complete system - then $\displaystyle r_i$ and $\displaystyle r'_j$ must be paired together. The remaining $\displaystyle p-1$ products will have to form a reduced system.

The argument I gave explains why that's impossible.

Saying that $\displaystyle r_1, \hdots, r_{p-1}$ is a complete system of residues $\displaystyle \mod p$ is just saying that $\displaystyle \{\overline{r_1},\hdots, \overline{r_{p-1}}\} = \{\overline{1}, \hdots, \overline{p-1}\}$, where $\displaystyle \overline{n}$ denotes the image of $\displaystyle n$ modulo $\displaystyle p$.

Thus for some permutation $\displaystyle \pi$ of $\displaystyle \{1,\hdots,p-1\}$ we will have :

$\displaystyle r_{\pi(1)} \equiv 1 \mod p$
...
$\displaystyle r_{\pi(p-1)} \equiv p-1 \mod p$

and taking the product of these congruences you get the answer to your question.

The product of the elements of any reduced system of residues mod p is = -1 (mod p). It doesn't matter whether you reduce mod p before or after taking the product.

5. Many thanks! You are so helpful. Also could you explain the pi(1) and pi(p-1) notation means and what "where n denotes the image of n modulo p" means?

6. You are welcome!

The image of $\displaystyle n$ modulo p is the equivalence class of $\displaystyle n$ under the equivalence relation $\displaystyle a \equiv b \mod p$. It is the image of $\displaystyle n$ in the group $\displaystyle \mathbb{Z}/n\mathbb{Z}$.

$\displaystyle \pi$ is a permutation; it just means that I have rearranged the indices.