Results 1 to 2 of 2

Math Help - Characterize integers, divisibility.

  1. #1
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Characterize integers, divisibility.

    ChallangeProblem.
    Characterize all the the positive integers n such that \phi(n)|n. ( \phi is Euler's Phi-Function.)


    Moderator edit: Approved challenge question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by melese View Post
    ChallangeProblem.
    Characterize all the the positive integers n such that \phi(n)|n. ( \phi is Euler's Phi-Function.)


    Moderator edit: Approved challenge question.

    Spoiler:
    If \displaystyle{n=p_1^{a_1}\cdot\ldots\cdot p_r^{a_r}}\,,\,\,p_i primes, a_i\in\mathbb{N} , and since \displaystyle{\phi(n)=n\prod\limits^r_{k=1}\left(1-\frac{1}{p_k}\right)} , we

    get that \displaystyle{\phi(n)\mid n\Longleftrightarrow 1=m\prod\limits^r_{k=1}\left(1-\frac{1}{p_k}\right)}\,,\,m\in\mathbb{N} , so the factors on the RHS are inverse

    to each other, and this means \displaystyle{\prod\limits^r_{k=1}\left(1-\frac{1}{p_k}\right)^{-1}=\prod\limits^r_{k=1}\frac{p_k}{p_k-1}\right)}\in\mathbb{N}.

    But the only prime that p_k-1 divides is 2 , unless p_k=2 and p_k-1=1 , in which case

    only the prime p_j=3 can possibly be so that (p_j-1)=2\mid 2=p_k , so n has to be of the form

    n=2^r3^s\,,\,r>0\,,\,s\geq 0 .


    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: August 3rd 2010, 02:31 PM
  2. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 15th 2009, 12:45 AM
  3. Replies: 4
    Last Post: February 24th 2008, 04:08 PM
  4. integers and divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2007, 10:40 AM
  5. Divisibility theory in the integers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 28th 2007, 09:10 PM

Search Tags


/mathhelpforum @mathhelpforum