Results 1 to 2 of 2

Thread: Phi Function

  1. #1
    Super Member
    Feb 2008

    Phi Function

    Let & denote the phi function

    Show that if m and n are not relatively prime, then &(m)&(n) < &(mn)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Oct 2007
    Well, if $\displaystyle (m,n)>1$ then they must have a common prime divisor $\displaystyle p$.

    Let $\displaystyle p^{\alpha}$ and $\displaystyle p^{\beta}$ be the greatest powers of p dividng $\displaystyle m$ and $\displaystyle n$ respectively, then $\displaystyle p^{\alpha+\beta}$ is the greatest power of p dividng $\displaystyle m\cdot n$.

    But then $\displaystyle \phi\left(p^{\alpha}\right)\cdot \phi\left(p^{\beta}\right) < \phi\left(p^{\alpha+\beta}\right)$ and you can finish it off by remembering $\displaystyle \phi$ is multiplicative.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 20
    Last Post: Nov 27th 2012, 05:28 AM
  2. Replies: 0
    Last Post: Oct 19th 2011, 04:49 AM
  3. Replies: 4
    Last Post: Oct 27th 2010, 05:41 AM
  4. Replies: 3
    Last Post: Sep 14th 2010, 02:46 PM
  5. Replies: 2
    Last Post: Sep 2nd 2010, 10:28 AM

Search Tags

/mathhelpforum @mathhelpforum