Remainder of the product of the relatively prime numbers

  1. Hi all, I had a problem, pls help me.

    Let [tex]b_1 < b_2 < \cdots < b_{\varphi(m)}[/tex] be the integers between 1 and m that are relatively prime to m (including 1), of course, [tex]\varphi(m)[/tex] is the number of integers between 1 and m that are relatively prime to m, and let [tex]B = b_1b_2b_3{\cdots}b_{\varphi(m)}[/tex] be their product.
    Please find a pattern for when [tex]B\equiv1 ({\bmod}\ m)[/tex] and when [tex]B\equiv-1 ({\bmod}\ m)[/tex].

    Thanks and Regards.
     
    Last edited: May 28, 2009
  2. jcsd
  3. CRGreathouse

    CRGreathouse 3,682
    Science Advisor
    Homework Helper

    Code (Text):
    ff(m)=centerlift(prod(b=2,m,if(gcd(m,b)==1,b,1),Mod(1,m)))
    for(m=2,20,print(m" "ff(m)))
    in Pari/gp gives
    Code (Text):
    2 1
    3 -1
    4 -1
    5 -1
    6 -1
    7 -1
    8 1
    9 -1
    10 -1
    11 -1
    12 1
    13 -1
    14 -1
    15 1
    16 1
    17 -1
    18 -1
    19 -1
    20 1
    Does that help?
     
  4. Thank you, I've gotten the similar table.
    Code (Text):

    m   phi rem
    1   1   1
    4   2   -1
    6   2   -1
    8   4   1
    9   6   -1
    10  4   -1
    12  4   1
    14  6   -1
    15  8   1
    16  8   1
    18  6   -1
    20  8   1
    21  12  1
    22  10  -1
    24  8   1
    25  20  -1
    26  12  -1
    27  18  -1
    28  12  1
    30  8   1
    32  16  1
    33  20  1
    34  16  -1
    35  24  1
    36  12  1
    38  18  -1
    39  24  1
    40  16  1
    42  12  1
    44  20  1
    45  24  1
    46  22  -1
    48  16  1
    49  42  -1
    50  20  -1
    51  32  1
    52  24  1
    54  18  -1
    55  40  1
    56  24  1
    57  36  1
    58  28  -1
    60  16  1
    62  30  -1
    63  36  1
    64  32  1
    65  48  1
    66  20  1
    68  32  1
    69  44  1
    70  24  1
    72  24  1
    74  36  -1
    75  40  1
    76  36  1
    77  60  1
    78  24  1
    80  32  1
    81  54  -1
    82  40  -1
    84  24  1
    85  64  1
    86  42  -1
    87  56  1
    88  40  1
    90  24  1
    91  72  1
    92  44  1
    93  60  1
    94  46  -1
    95  72  1
    96  32  1
    98  42  -1
    99  60  1
     
    but I still can't find the ppattern, and I have only found that if 4 does not divide [tex]\phi(m)[/tex] then [tex]B{\equiv}-1[/tex], and if [tex]B{\equiv}1[/tex], there must be that 4 divides [tex]\phi(m)[/tex]
     
    Last edited: May 29, 2009
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?