Results 1 to 6 of 6

Math Help - remainder of the product of the relatively prime numbers

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    remainder of the product of the relatively prime numbers

    Hi all, I had a problem, pls help me.
    Let b_1 < b_2 < \cdots < b_{\varphi(m)} be the integers between 1 and m that are relatively prime to m (including 1), of course, \varphi(m) is the number of integers between 1 and m that are relatively prime to m, and let B = b_1b_2b_3{\cdots}b_{\varphi(m)} be their product.
    Please find a pattern for when B\equiv1 ({\bmod}\ m) and when B\equiv-1 ({\bmod}\ m).
    Thanks and Regards.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Getting started...

    Define B_m="the product of the totatives of m"= \prod_{(k,m)=1}k as per your statement.

    It is known that k has an inverse modulo m iff (k,m)=1, therefore, every k in the above product is either it's own inverse, k^2\equiv1(\bmod m), or can be "matched" with its inverse kk^{-1}\equiv1(\bmod m)

    The "matched" factors disappear from the product, so B_m=\prod_{k^2\equiv1}k which is always inclusive of 1 and m-1 (do you see why?)

    Also, since \phi(m) is always even, and we've removed an even number of factors, there are always an even number of k's which are their own inverse modulo m, for any m.

    So, what is the product of these self-inverses? Well, if a and b are both self-inverses then a^2b^2=(ab)^2\equiv1(\bmod m), so ab\equiv\pm1(\bmod m). This proves that B_m\equiv\pm1(\bmod m) for all m.

    Now, which is which? Overwhelmingly, B_m\equiv-1(\bmod m), the exceptions being m=8,12,15,16,18,24,... I am having difficulty picking out a pattern in this sequence, and I don't believe any kind of formula can express it. However, we've shown that our product is the product of n pairs of self-inverses, B_m=(ab)_1(ab)_2...(ab)_n . For B_m\equiv+1(\bmod m), there must be an even number of pairs ab\equiv-1(\bmod m)

    This is getting somewhat beyond me, here. Are there any known rules dictating the square roots of 1 modulo m?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Reading up...

    Always learning new stuff

    If m has a primitive root, then all totatives of m can be expressed as powers of that root. For example, the first primitive root of 22 is 7, and 7^n\equiv 1,7,5,13,3,21,15,17,9,19, for n=0,1,2,...,\phi(m)-1. Since 7^a7^b=7^{a+b}, then 7^a7^b\equiv 1 if and only if a+b is a multiple of \phi(m). Therefore 1\equiv7^0 and 21\equiv7^5 is the only self-inverse modulo 22. Generalizing, if m has a primitive root p, then p^0 and p^{\phi(m)/2} are the only self-inverses modulo m.

    Therefore, if m has a primitive root, its only self-inverses are the trivial 1 and m-1, whose product is -1, so B_m\equiv-1. So if B_m=+1, m does not have a primitive root. However the converse is not true.

    The first few numbers lacking a primitive root are: 8,12,15,16,20,21,... But B_{20} and B_{21} are the first examples of numbers in this sequence for which B_m\equiv-1(\bmod m)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Gaaaaahhh!

    I made an error in calculation. B_{20} and B_{21} are in fact \equiv+1 and the converse of the above theorem is in fact true (I just haven't yet worked out the proof.) Your problem has to do with a generalization of Wilson's Theorem: Wilson's Theorem -- from Wolfram MathWorld

    It sucks to be wrong, but I think I got pretty far.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    3
    Quote Originally Posted by Media_Man View Post
    I made an error in calculation. B_{20} and B_{21} are in fact \equiv+1 and the converse of the above theorem is in fact true (I just haven't yet worked out the proof.) Your problem has to do with a generalization of Wilson's Theorem: Wilson's Theorem -- from Wolfram MathWorld

    It sucks to be wrong, but I think I got pretty far.
    Thank you spending so much time to do me a big favor, I'm so glad getting it, but I can not prove completely Gauss's generalization of Wilson's theorem.
    I only proved:
    if m = 4, p^n or 2p^n, which p is an odd prime, there must be B\equiv-1({\bmod}\ m), since there is no other one satisfies the congruence x^2\equiv1({\bmod}\ m), excepting 1 and m - 1, I can not prove B\equiv1({\bmod}\ m) when m is other integers.
    Last edited by whodsow; May 29th 2009 at 11:13 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2009
    Posts
    3
    Last edited by whodsow; May 29th 2009 at 11:54 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 1
    Last Post: September 29th 2011, 11:26 AM
  3. [SOLVED] Remainder when large numbers divided
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 27th 2011, 07:13 PM
  4. Finding remainder in non-prime congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 4th 2009, 06:38 PM
  5. Product of two prime cycles
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 13th 2009, 09:28 PM

Search Tags


/mathhelpforum @mathhelpforum