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

Question from the proof in euler's forumla

  1. Mar 14, 2011 #1
    Let b1,b2,...bn be the integers between 1 and m that are relative prime to m (including 1), and let B = b1*b2*...*bn be their product. The quantity B came up during the proof of euler formula. a^n = 1 (mod m), where n is number of integers between 1 and m that relative prime to m.

    How can I show B=1 (mod m ) or B = -1(mod m)?
     
  2. jcsd
  3. Mar 14, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    Have you seen Wilson's theorem? This states that (p-1)!=-1 (mod p) for prime p.

    Can you adjust the proof so that it also works in this case?
     
  4. Mar 14, 2011 #3
    I have tried, but fail in the last step:
    In Wilson's proof, the number satisfy a^2=1(mod p) -> (a-1)(a+1) = p*n. Since 0<=a<p
    a= 1 or p-1 only. So for 2,3,...,p-2, I can group them into pairs without repeat such that the pair product = 1 (mod p)...

    But in my problem, the number satisfy a^2=1(mod m) does not imply a=1 or m-1 since m is a composite number. (e.g. 3^2=1(mod 8))

    I also modify my proof. Consider B^2=b1^2*b2^2*...bn^2. I have showed that for each bi, there exist unique bj such that bi*bj=1 (mod m) (similar to Wilson’s proof). Although we don't know bi is equal to bj or not.

    So I divide the number into 2 groups,
    1st group: bi*bj=1 (mod m) for i <>j
    2nd group: bi*bj=1 (mod m) for i = j

    So B^2 = 1 (mod m) but the same problem occurs,
    It cannot be concluded that B= 1 or -1(mod m)
     
  5. Mar 14, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    Well, you could show the following:

    For each bi, there exists a bj such that bibj=1 (mod m). If bi happens to equal bj, then there exists a br such that bibr=-1 (mod m).

    So you can group the product into pairs again. Some pairs will multiply to 1 and some will multiply to -1.
     
  6. Mar 15, 2011 #5
    I get it! Thanks.
     
  7. Mar 15, 2011 #6
    If bj^2 = 1 mod m then bj *(m -bj) = -1 mod m
     
    Last edited: Mar 15, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Question from the proof in euler's forumla
  1. Euler's polynomial proof (Replies: 14)

  2. Question on a proof. (Replies: 3)

Loading...