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.
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.
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.
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.
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.