Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Remainder of the product of the relatively prime numbers

  1. May 28, 2009 #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. May 28, 2009 #2

    CRGreathouse

    User Avatar
    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. May 29, 2009 #3
    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
  5. May 29, 2009 #4
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Remainder of the product of the relatively prime numbers
Loading...