Results 1 to 7 of 7

Thread: Lagranges Theorem

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    170

    Lagranges Theorem

    So we have $\displaystyle \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 $\displaystyle n $ is equal to the totient product of their prime factors. So then $\displaystyle \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 $\displaystyle \phi(n) $ defined for integers $\displaystyle \leq n $ as opposed to just integers $\displaystyle < n $. Because a number is never coprime with itself right?
    Last edited by particlejohn; Aug 31st 2008 at 09: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 $\displaystyle \phi(n) $ defined for integers $\displaystyle \leq n $ as opposed to just integers $\displaystyle < n $. Because a number is never coprime with itself right?
    You are right. It makes no difference.
    I would guess is the problem with $\displaystyle n=1$.
    Since the set $\displaystyle \{ 1\leq x < n\}$ would be empty.
    And then $\displaystyle \phi(1) = 0$.
    But we want to define it as $\displaystyle \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 $\displaystyle \phi(8) = 4 \neq \phi(2) \times \phi(2) \times \phi(2) = 1 $. Or does it mean $\displaystyle \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 $\displaystyle \phi(8) = 4 \neq \phi(2) \times \phi(2) \times \phi(2) = 1 $.
    That is wrong!
    The rule $\displaystyle \phi(ab)=\phi(a)\phi (b)$ holds when $\displaystyle \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 $\displaystyle \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 $\displaystyle n $ is equal to the totient product of their prime factors. So then $\displaystyle \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 $\displaystyle \phi(n) $ defined for integers $\displaystyle \leq n $ as opposed to just integers $\displaystyle < n $. Because a number is never coprime with itself right?
    Ok this is for distinct prime factors. $\displaystyle 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 :

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

    where $\displaystyle p_i$ is a prime divisor of n.

    For example, $\displaystyle 140=2^2 \cdot 5 \cdot 7$
    $\displaystyle 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: Apr 20th 2010, 02:57 AM
  2. Lagranges Theorem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jan 5th 2010, 03:56 PM
  3. Lagranges theorem
    Posted in the Advanced Algebra Forum
    Replies: 20
    Last Post: Jan 5th 2010, 05:32 AM
  4. Lagranges mean value Theorem
    Posted in the Calculus Forum
    Replies: 12
    Last Post: Dec 27th 2009, 11:54 PM
  5. Minimizing with Lagranges' Multipliers
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Sep 19th 2007, 01:01 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum