$a_1 a_1', a_2 a_2', ..., a_n a_n'$ is not a reduced modulo system $\mod p$.

Question

If $a_1, a_2, ..., a_n$ is a reduced residue system $\mod p$ and $a_1', a_2', ..., a_n'$ is another reduced residue system $\mod p$ then $a_1 a_1', a_2 a_2', ..., a_n a_n'$ is not a reduced modulo system $\mod p$.

Not able to show a counter to it. Help Needed.

Answer 1

Since $\{a_1,a_2,\ldots,a_n\}$ is a reduced residue system modulo $p$, we know that modulo $p$, $\{a_1,a_2,\ldots,a_n\}$ is a permutation of $\{1,2,\ldots,p-1\}$.

Knowing this, we have by Wilson's Theorem $\prod_{k=1}^na_k\equiv1\times2\times\ldots\times (p-1)\equiv -1(\mathrm{mod}~p)$.

Now $\prod_{k=1}^na_ka'_k\equiv\left(\prod_{k=1}^na_k\right)\left(\prod_{k=1}^na'_k\right)\equiv(-1)^2\equiv1(\mathrm{mod}~p)$

Since the first result holds for any reduced residue system, we can conclude that $\{a_1a'_1,a_2a'_2,\ldots,a_na'_n\}$ is not a reduced residue system modulo $p$.