Results 1 to 2 of 2

Thread: Characterize integers, divisibility.

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

    Characterize integers, divisibility.

    ChallangeProblem.
    Characterize all the the positive integers $\displaystyle n $ such that $\displaystyle \phi(n)|n$. ($\displaystyle \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
    3
    Quote Originally Posted by melese View Post
    ChallangeProblem.
    Characterize all the the positive integers $\displaystyle n $ such that $\displaystyle \phi(n)|n$. ($\displaystyle \phi $ is Euler's Phi-Function.)


    Moderator edit: Approved challenge question.

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

    get that $\displaystyle \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 \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 $\displaystyle p_k-1$ divides is $\displaystyle 2$ , unless $\displaystyle p_k=2$ and $\displaystyle p_k-1=1$ , in which case

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

    $\displaystyle 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: Aug 3rd 2010, 01:31 PM
  2. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2009, 11:45 PM
  3. Replies: 4
    Last Post: Feb 24th 2008, 03:08 PM
  4. integers and divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 7th 2007, 09:40 AM
  5. Divisibility theory in the integers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 28th 2007, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum