Math Help - complete residue modulo

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, $r_1\hdots r_n \equiv r'_1\hdots r'_n \equiv -1 \mod p$.

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

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

The argument I gave explains why that's impossible.

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

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

$r_{\pi(1)} \equiv 1 \mod p$
...
$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 $n$ modulo p is the equivalence class of $n$ under the equivalence relation $a \equiv b \mod p$. It is the image of $n$ in the group $\mathbb{Z}/n\mathbb{Z}$.

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