0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please see my edit to learn some MathJax features. $\endgroup$ – Arnaud Mortier Jul 4 '18 at 13:00
  • 1
    $\begingroup$ What does Wilson Theorem say, first of all? You won't get far if you don't use the hint. Please include that in the question, try using it and then say where you are stuck. $\endgroup$ – Arnaud Mortier Jul 4 '18 at 13:02
  • $\begingroup$ Using the Wilson is pointless at this stage because I can't even comprehend what I am trying to proof.And why this proof(that the product is not complete sys. of residues) by itself is "true" $\endgroup$ – user6394019 Jul 4 '18 at 13:08
  • $\begingroup$ It's not pointless, write it down and try to figure out how it is related to the problem. Take $p=3$ and see what happens. See this on what to do when you have no clue on a question. $\endgroup$ – Arnaud Mortier Jul 4 '18 at 13:17
  • $\begingroup$ @ArnaudMortier For a1b1; a2b2; : : : ; apbp to be a complete system of residues modulo p under the assumption that ap ≡ bp ≡ 0 (mod p) it must be that (a1b1) · (a2b2) · · · (ap−1bp−1) ≡ (p − 1)! ≡ −1 (mod p); by Wilson’s theorem. To show that a1b1; a2b2; : : : ; apbp does not form a complete system of residues we show that (8.67) does not hold. Indeed, by Wilson’s theorem we have that a1 · a2 · · · ap−1 ≡ b1 · b2 · · · bp−1 ≡ −1 (mod p): Hence, (a1b1) · (a2b2) · · · (ap−1bp−1) ≡ (−1)2 ≡ 1 (mod p): As p > 2 we have that −1 6≡ 1 (mod p). The claim follows. $\endgroup$ – user6394019 Jul 4 '18 at 13:28
1
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ putting it in that sense it's clear to me now that it contracdicts the theorem! thank you! $\endgroup$ – user6394019 Jul 4 '18 at 14:01
  • 1
    $\begingroup$ That's correct. Have a look at the proof of Wilson's Theorem and see how $(p-1)!$ and the product $a_1\cdot a_2 \dotsm a_{p-1}$ relate to each other, it's all in the inverses. $\endgroup$ – Daniel Buck Jul 4 '18 at 14:10
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't think that's helping the OP to do it all for them where they couldn't even see how Wilson was related to the problem. $\endgroup$ – Arnaud Mortier Jul 4 '18 at 13:29
  • $\begingroup$ In this case, short of a private chat, my sense was that hints would not be sufficient. $\endgroup$ – quasi Jul 4 '18 at 13:33
  • $\begingroup$ Apparently they were, given the OP's last comment :) $\endgroup$ – Arnaud Mortier Jul 4 '18 at 13:34
  • $\begingroup$ Yep, the OP transformed! I'll delete my answer (in favor of yours). $\endgroup$ – quasi Jul 4 '18 at 13:35
  • $\begingroup$ Oh, so the OP's comment was a book solution! Hence, I'll reinstate my answer. $\endgroup$ – quasi Jul 4 '18 at 13:38
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.