1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that phi(a^n - 1) is divisible by n

  1. Mar 19, 2008 #1

    xax

    User Avatar

    As the title says, for any a>1 and n>0
     
  2. jcsd
  3. Mar 22, 2008 #2
    Set [tex] a^n=1+M[/tex]. Consequently [tex]a^n\equiv 1ModM[/tex] and is the smallest n for a>1, n>0. It also follows from the last equation that a belongs to the reduced residue group of order [tex]\phi{M}[/tex]. Consequently by LaGrange's Theorem, n is a divisor of the order of the group.
     
    Last edited: Mar 22, 2008
  4. Mar 22, 2008 #3
    You cannot say that for sure, or I am wrong?
     
  5. Mar 23, 2008 #4
    al-mahed: You cannot say that for sure, or I am wrong?

    I can say what I meant for sure. However, the way I wrote it, "And is the smallest n for a>1,
    n>0, which you have put in red, this, I see, is confusing. It is not what I am asserting, but is repeating the conditions given by xax, "As the title says, for any a>1 and n>0."

    So that since n >0, and a>1, which is a very minimal restriction, we know we have a positive value here which I deliberately set: [tex] a^n=1+M[/tex] This is the smallest value of n which can be used to achieve the required non-trivial equation: [tex]a^n\equiv 1ModM[/tex] since the left side is, in fact, just 1 more than M.

    Thanks for the comment, it shows someone is reading this.
     
    Last edited: Mar 23, 2008
  6. Mar 23, 2008 #5

    xax

    User Avatar

    robert, why does m = n and [tex] a^n=1+m[/tex]? This is exactly what I need to prove?
    I understood why [tex] a^n=1+M[/tex], but did not understand why M=n.
    Thanks
     
  7. Mar 23, 2008 #6
    M does not equal n. M=(a^n-1). Thus the order of the group [tex]\phi{M}=\phi(a^n-1)[/tex]. n is the order of the element a.
     
  8. Mar 23, 2008 #7

    xax

    User Avatar

    you've saved me again robert, thanks.
     
  9. Mar 24, 2008 #8
    What you have to do sometimes is look at problems. Say, 2^4 =16. So we set the modulus at 15. Thus we have 2^4 ==1 Mod 15.

    Now phi(15)= phi(5)*phi(3) = 4x2 = 8. That means that the reduced residue group of elements relatively prime to 15 are 8 in number. They are the elements that form the multiplicative group. (3 for example is not in this group since there is no solution to 3X==1 Mod 15. So 3 has no inverse.)

    In fact, the eight elements are: 1, 2, 4, 7, 8, 11, 13, 14. Each one of these group elements has an inverse. For example: 1*1==1 Mod 15, 2*8=16==1 Mod 15, 4*4==1 Mod 15, 7*13 = 91==1 Mod 15, and so forth.

    The theorem then states that the order of the element, which is 4, divides the order of the group which is 8.
     
    Last edited: Mar 24, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove that phi(a^n - 1) is divisible by n
  1. Divisibility of n by 6 (Replies: 10)

Loading...