Results 1 to 2 of 2

Math Help - Divisibility

  1. #1
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Divisibility

    Given that d|n, show that phi(d)|phi(n) if n is a power of a prime. If n=p^k, then phi(n)=p^k-p^(k-1), but I can't make the leap to showing divisibility. Help, please!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by tarheelborn View Post
    Given that d|n, show that phi(d)|phi(n) if n is a power of a prime. If n=p^k, then phi(n)=p^k-p^(k-1), but I can't make the leap to showing divisibility. Help, please!
    If n=p^k then d\mid n\implies d=p^\ell,\text{ }1\leqslant \ell\leqslant k. Thus, \phi(p^\ell)=p^\ell-p^{\ell-1}=p^{\ell-1}\left(p-1\right) and \phi(n)=p^k-p^{k-1}=p^{k-1}(p-1). Thus, \frac{\phi(n)}{\phi(d)}=\frac{p^{k-1}(p-1)}{p^{\ell-1}(p-1)}=p^{k-\ell}\in\mathbb{N}. It follows that \phi(d)\mid \phi(n)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum