Results 1 to 6 of 6

Thread: complete residue modulo

  1. #1
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18
    How do you know that (p-1)! is congruent or equal to r1 * r2 * ... * rp
    and congruent to r'1 * r'2 * ... * r'p?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    From
    In limbo
    Posts
    18
    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?
    Last edited by comssa; Oct 4th 2009 at 11:25 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complete Residue Systems Problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 22nd 2010, 04:25 PM
  2. Reduced residue system modulo m
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jan 20th 2010, 08:12 PM
  3. Distinct residue modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 24th 2009, 02:08 PM
  4. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Dec 1st 2009, 09:04 AM
  5. residue modulo - wilson's theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 19th 2009, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum