Proving that a product of 2 complete residue systems of modulo p is not complete (modulo p)

Question

Given that $p$ is a prime and $p>2$ and let $a_1, \ldots , a_p$ and $b_1, \ldots , b_p$ be two complete systems of residues modulo $p$ where $a_p \equiv b_p \equiv 0 \pmod p$. Prove that $a_1b_1, \ldots , a_pb_p$ is not a complete system of residues modulo $p$.

hint: Wilson Theorem

I can't even grasp why it is not a complete system of residues, because by definition if $p\mid a_p$ and $p\mid b_p$ then the condition $p\mid a_pb_p$ must arise, so how come it is not a complete system? I am thinking that maybe my comprehension of system\class of residues is wrong...

Answer 1

The residue classes modulo $p$ form a field. As such every element $a$ in a complete residue system, disregarding $0$, has a multiplicative inverse $a^{-1}$. Note these $a$ and $a^{-1}$ are distinct from each other, consider why this is true, apart from the two elements $1$ and $p-1\equiv-1\pmod{p}$, which are self inverse, also understand why this is true. Note also $(p-1)\cdot 1\equiv-1\pmod{p}$ (from which Wilson's Theorem, $(p-1)!\ \equiv \ -1\pmod {p}$, follows after some work).

Assuming $a_p \equiv b_p \equiv 0 \pmod p$, then since $$a_1\cdot a_2 \dotsm a_{p-1}\equiv -1\pmod{p}$$ and $$b_1\cdot b_2 \dotsm b_{p-1}\equiv -1\pmod{p}$$ by Wilson's Theorem. Now form the product $$ (a_1\cdot a_2 \dotsm a_{p-1})\cdot (b_1\cdot b_2 \dotsm b_{p-1})\equiv-1\cdot-1=1\pmod{p} $$ so $$ (a_1b_1)\cdot (a_2 b_2)\dotsm (a_{p-1} b_{p-1})\equiv 1\pmod{p} $$ so what does this tell us about the system $a_1b_1$, $a_2 b_2,\dotsc, a_{p-1} b_{p-1}$, $a_pb_p$?

Answer 2

If $m$ is a positive integer, a complete residue system, mod $m$, is a set of $m$ integers, which, when reduced mod $m$, is equal (as a set) to the set of integers between $0$ and $m-1$ inclusive.

For example, the sets $\{-3,1,14,8,-20\}$ and $\{7,6,13,35,-1\}$ are both complete residue systems, mod $5$.

Now recall Wilson's Theorem: If $p$ is prime, then $(p-1)!\equiv -1\;(\text{mod}\;p)$.

For the question at hand . . .

Let $p$ be an odd prime.

Suppose $a_1,...,a_p$ and $b_1,...,b_p$ are complete residue systems, mod $p$, with $a_p$ and $b_p$ both congruent to zero, mod $p$,

Then the sequences $a_1,...,a_{p-1}$ and $b_1,...,b_{p-1}$, reduced mod $p$, are permutations of $1,...,p-1$, hence, by Wilson's Theorem, $$ \prod_{k=1}^{p-1}a_k\equiv -1\;(\text{mod}\;p) \\ \prod_{k=1}^{p-1}b_k\equiv -1\;(\text{mod}\;p) $$ which implies $$\prod_{k=1}^{p-1}a_kb_k\equiv 1\;(\text{mod}\;p)$$ hence, since $p$ is odd, $$\prod_{k=1}^{p-1}a_kb_k\not\equiv -1\;(\text{mod}\;p)$$ so by Wilson's Theorem, the sequence $a_1b_1,...,a_{p-1}b_{p-1}$, reduced mod $p$, is not a permutation of $1,...,p-1$.

Then, since $a_pb_p$ is congruent to zero, mod $p$, it follows that $a_1b_1,...,a_pb_p$ is not a complete residue system, mod $p$.

Answer 3

Hint:

Wilson's theorem says that

IF $x_1,\ldots, x_{p-1}$ is a complete residue system except that it doesn't contain $0$, THEN (something happens)

What you want to prove is that

(some set) is NOT a residue system.

The relation between the two is obvious: use proof by contradiction.

If the stated set was a residue system, then (we could apply Wilson's theorem).

On the way you are going to need to apply Wilson's theorem to both residue systems $a$ and $b$.

Answer 4

Hint to help your understanding:

$p|a_p$ and $p|b_p$ but $p\not\mid a_i$ and $p\not\mid b_i$ for $i \ne p$.

If we do this $\mod 3$ and let $\{a_1,a_2,a_3\} = \{1,2, 3\}$ be a complete residue system. And $\{b_1,b_2,b_3\} = \{4,5,6\}$ also be a complete residue system.

Then we get $\{a_1b_1, a_2b_2, a_3b_3\} = \{4, 10, 18\}$. Is that a complete residue system?

Notice that $a_1b_1 \equiv a_2b_2 \equiv 1 \mod 3$ and $a_ib_i \equiv 2 \mod 3$ can never happen for any $i$. So we have two residues that are congruent to $1$ and zero residues that are congruent to $2$.

So, no, it is not complete.

Wilson's theorem states that $a_1a_2\equiv (3-1)! \equiv -1 \mod 3$ and that $b_1b_2 \equiv (3-1)! \equiv -1 \mod 3$. And, what do you know, $a_1a_2 = 1*2 = 2!\equiv -1 \mod 3$ and $b_1*b_2=4*5 = 20\equiv 2 =2!\equiv -1 \mod 3$. So that is true.

If $\{a_ib_i\}$ were a complete residue theorem we would have $(a_1b_1)*(a_2b_2) \equiv -1 \mod 3$.

Does it?

$(a_1b_1)*(a_2*b_2) \equiv 4*10\equiv 40=39+1 \equiv 1 \mod 3$. And $1 \not \equiv -1\mod 3$.

So this is not a complete residue system.

Not only could we tell by examing it directly, we could also tell by using Wilson's theorem.

...

Can we do the same for any other prime $p>$? Oh, and will this be true for other residue systems?

....

One more hint: $(a_1b_2)*(a_2*b_2)\equiv (a_1a_2)(b_1b_2) \equiv (-1)*(-1)\mod 3$.