Results 1 to 7 of 7

Math Help - Lagranges Theorem

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

    Lagranges Theorem

    So we have  \phi(n) = \prod_{i=1}^{k}  \phi(p_{i}^{e_{i}}) = \prod_{i=1}^{k} p_{i}^{e_{i}-1}(p_{i}-1) . So basically what it is saying that the number of numbers coprime to  n is equal to the totient product of their prime factors. So then  \phi(8) = 4 \neq \phi(2) \cdot \phi(2) \cdot \phi(2) . What's wrong with this (am I interpreting this incorrectly)? Also why is  \phi(n) defined for integers  \leq n as opposed to just integers  < n . Because a number is never coprime with itself right?
    Last edited by particlejohn; August 31st 2008 at 10:40 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by particlejohn View Post
    Also why is  \phi(n) defined for integers  \leq n as opposed to just integers  < n . Because a number is never coprime with itself right?
    You are right. It makes no difference.
    I would guess is the problem with n=1.
    Since the set \{ 1\leq x < n\} would be empty.
    And then \phi(1) = 0.
    But we want to define it as \phi(1)=1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    170
    Sorry I am using Lagrange's Theorem, but the above is not Lagrange's Theorem.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2008
    Posts
    170
    But  \phi(8) = 4 \neq \phi(2) \times \phi(2) \times \phi(2) = 1 . Or does it mean  \phi(2^{3}) ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by particlejohn View Post
    But  \phi(8) = 4 \neq \phi(2) \times \phi(2) \times \phi(2) = 1 .
    That is wrong!
    The rule \phi(ab)=\phi(a)\phi (b) holds when \gcd(a,b)=1.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2008
    Posts
    170
    Quote Originally Posted by particlejohn View Post
    So we have  \phi(n) = \prod_{i=1}^{k}  \phi(p_{i}^{e_{i}}) = \prod_{i=1}^{k} p_{i}^{e_{i}-1}(p_{i}-1) . So basically what it is saying that the number of numbers coprime to  n is equal to the totient product of their prime factors. So then  \phi(8) = 4 \neq \phi(2) \cdot \phi(2) \cdot \phi(2) . What's wrong with this (am I interpreting this incorrectly)? Also why is  \phi(n) defined for integers  \leq n as opposed to just integers  < n . Because a number is never coprime with itself right?
    Ok this is for distinct prime factors.  8 = 2^{3} which is not distinct prime factors.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Another formula is :

    \phi(n)=n \prod_{i=1}^k \left(1-\frac{1}{p_i}\right)

    where p_i is a prime divisor of n.

    For example, 140=2^2 \cdot 5 \cdot 7
    p_1=2 ~,~ p_2=5 ~,~ p_3=7
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: April 20th 2010, 03:57 AM
  2. Lagranges Theorem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 5th 2010, 04:56 PM
  3. Lagranges theorem
    Posted in the Advanced Algebra Forum
    Replies: 20
    Last Post: January 5th 2010, 06:32 AM
  4. Lagranges mean value Theorem
    Posted in the Calculus Forum
    Replies: 12
    Last Post: December 28th 2009, 12:54 AM
  5. Minimizing with Lagranges' Multipliers
    Posted in the Calculus Forum
    Replies: 3
    Last Post: September 19th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum