Results 1 to 6 of 6

Math Help - 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, r_1\hdots r_n \equiv r'_1\hdots r'_n \equiv -1 \mod p.

    But r_1r'_1 \hdots r_nr'_n \equiv (-1)^2 \equiv 1 \mod p.

    So 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 r's is \equiv 0 (say r_i) and similarily for one of the r' 's (say r'_j). So if we want to avoid having two of the r\: r' 's congruent to 0 - because then we obviously couldn't get a complete system - then r_i and r'_j must be paired together. The remaining p-1 products will have to form a reduced system.

    The argument I gave explains why that's impossible.

    Saying that r_1, \hdots, r_{p-1} is a complete system of residues \mod p is just saying that \{\overline{r_1},\hdots, \overline{r_{p-1}}\} = \{\overline{1}, \hdots, \overline{p-1}\}, where \overline{n} denotes the image of n modulo p.

    Thus for some permutation \pi of \{1,\hdots,p-1\} we will have :

    r_{\pi(1)} \equiv 1 \mod p
    ...
    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; October 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 n modulo p is the equivalence class of n under the equivalence relation a \equiv b \mod p. It is the image of n in the group \mathbb{Z}/n\mathbb{Z}.

    \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: January 20th 2010, 08:12 PM
  3. Distinct residue modulo
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 24th 2009, 02:08 PM
  4. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  5. residue modulo - wilson's theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum