Results 1 to 6 of 6

Math Help - Similar to Wilson's Theorem

  1. #1
    Member
    Joined
    Sep 2006
    Posts
    221

    Similar to Wilson's Theorem

    Suppose that m is an int. and has primitive roots; then, we know that the product of the pos. integers less than m and also relatively prime to m is congruent to -1 (mod m). (Notice that if m were prime, this would just be Wilsonís Theorem).

    a.) Give an example of this theorem for a m (a compositive number) that is greater than 10

    b.) Give an example that shows the result of this theorem will not always be true if m doesn't have primitive roots.

    c.) Prove the theorem.
    HINT: for all primes p, if gcd(a,p) = 1, then a^((p-1)/2) = +/- 1 (mod p)
    This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
    then r^(phi(m)/2) = -1 (mod m)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2005
    Posts
    21

    Lightbulb

    Quote Originally Posted by Ideasman View Post
    a.) Give an example of this theorem for a m (a compositive number) that is greater than 10

    b.) Give an example that shows the result of this theorem will not always be true if m doesn't have primitive roots.
    a) Let m=14; then the product (mod 14) is 3*5*9*11*13=15*99*13=1*1*-1=-1 (because 98=7*14)

    b) Let m=12; sqrt(12)=2sqrt(3), so 12 does not have primitive roots, and the product (mod 12) is 5*7*11=35*11=-1*-1=1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    c.) Prove the theorem.
    HINT: for all primes p, if gcd(a,p) = 1, then a^((p-1)/2) = +/- 1 (mod p)
    What theorem? Wilson's theorem? I do not know what you want me to prove.
    This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
    then r^(phi(m)/2) = -1 (mod m)
    r^phi(m) = 1 (mod m)
    Thus,
    r^(phi(m))-1=0(mod m)
    If m>2 then phi(m) is even, thus,
    [r^(phi(m)/2) - 1][r^(phi(m)/2 + 1] = 0 (mod m)
    We need to show that none of these two factors are divisors or zero.
    Once we show that then either the first or second is zero.
    Note it cannot be the first because that implies:
    r^(phi(m)/2) = 1 (mod m).
    And phi(m)/2 < phi(m) a contradiction because phi(m)=ord_m(r)
    Thus,
    r^(phi(m)/2) = -1 (mod m)
    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2006
    Posts
    221
    Thanks for the proof, TPH, but I have to prove

    "Suppose that m is an int. and has primitive roots; then, we know that the product of the pos. integers less than m and also relatively prime to m is congruent to -1 (mod m). (Notice that if m were prime, this would just be Wilsonís Theorem)."

    That part.

    The professor, then, suggests to prove that by using the following:

    "This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
    then r^(phi(m)/2) = -1 (mod m)"

    So using THAT, you prove the first theorem that I need to find a proof for.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    Thanks for the proof, TPH, but I have to prove

    "Suppose that m is an int. and has primitive roots; then, we know that the product of the pos. integers less than m and also relatively prime to m is congruent to -1 (mod m). (Notice that if m were prime, this would just be Wilson’s Theorem)."

    That part.

    The professor, then, suggests to prove that by using the following:

    "This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
    then r^(phi(m)/2) = -1 (mod m)"

    So using THAT, you prove the first theorem that I need to find a proof for.
    I expect you two things about primitive roots.

    Theorem 1: If r is a primitive root for a number m>1 then the set {r,r^2,r^3,...,r^[phi(m)]} are exactly all the integers relatively prime to m (and less than m).

    The above theorem is the fundamental property of the primitive root.

    Theorem 2: If m>2 then phi(m) is even.

    Theorem 3: If r is a primitive root then r^[phi(m)] =1 (mod m).

    Actually that is basically the definition of what a primitve root is.

    Okay, here is the fundamental part in this proof.
    If A_1,A_2,...,A_[phi(m)] are all the integers >=1 and relatively prime to m (and less than it) then there product is,
    A_1*A_2*...*A_[phi(m)]
    But by Theorem 1, it is r*r^2*....*r^[phi(m)]
    (Note necessarily in that order. But they can be rearranged by Dirichlet's Pigeonhole Principle).

    Now follow the attachment. (That "p" should really be a "m" in the last line).
    Attached Thumbnails Attached Thumbnails Similar to Wilson's Theorem-picture1.gif  
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Ideasman View Post
    "This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
    then r^(phi(m)/2) = -1 (mod m)"
    We still never proved this. My professor suggests the following simple and elegant proof.

    Let r be a primitive root of m. Then there exists a positive integer k such that r^k = -1 (mod m). Now what can k be? Note if k<phi(m)/2 then (r^k)^2 = r^(2k) = 1 (mod m) with 2k<phi(m). Contradicting the fact the r is a primitive root. If k>phi(m)/2 then the order of an interger must divide phi(m) [This is a theorem]. But then that is impossible because phi(m)/2 does not divide phi(m). Thus k=phi(m)/2 is the only possible exponent for r to produce -1 under modulo m.
    Q.E.D.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 30th 2011, 10:26 AM
  2. Regarding Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 5th 2010, 01:53 PM
  3. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2010, 01:07 PM
  4. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 02:30 AM
  5. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 7th 2008, 11:41 AM

Search Tags


/mathhelpforum @mathhelpforum