Results 1 to 5 of 5

Thread: Euler's phi function

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Euler's phi function

    I will denote the phi function to be &.
    For example, &(36) = 36(1-1/2)(1-1/3) = 12

    Find all n such that &(n) = 8.

    How is this done w/o just guessing and checking? Thanks...
    Last edited by jzellt; Apr 7th 2010 at 10:41 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by jzellt View Post
    I will denote the phi function to be &.
    For example, &(36) = 36(1-1/2)(1-1/3) = 12

    Find all n such that &(n) = 8. Find them and prove there is no more.

    How is this done w/o just guessing and checking? Thanks...
    $\displaystyle \phi(n) = 8 $

    as you know

    $\displaystyle \phi(p^n) = (p^n - p^{n-1}) $

    so n is a multiple of 2 just since if it is multiple from another prime it will be a divisor of phi(n) is it ok for now

    so n contains just 2

    suppose $\displaystyle n = 2^t $

    $\displaystyle \phi(2^t) = 2^t - 2^{t-1} = 8 $

    $\displaystyle 2^{t-1}(2-1) = 8 \rightarrow t-1=3 $

    so

    $\displaystyle n= 2^4 $
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    I thought I understood, but I guess I'm still a bit confused...

    What if I had to find all n such that &(n) = 2?

    The above seems to calculate how many n, but not what each n is.

    Can you elaborate...

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    "so n is a multiple of 2 just since if it is multiple from another prime it will be a divisor of phi(n) is it ok for now"

    this is wrong statement I forgot number theory sorry

    phi(5) = 4 and 2 is not a divisor of 5



    phi(15) = 2(4) = 8

    there is another solutions

    I can't figure exactly how I can solve it sorry
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Amer View Post
    $\displaystyle \phi(n) = 8 $

    as you know

    $\displaystyle \phi(p^n) = (p^n - p^{n-1}) $

    so n is a multiple of 2 just since if it is multiple from another prime it will be a divisor of phi(n) is it ok for now

    so n contains just 2

    suppose $\displaystyle n = 2^t $

    $\displaystyle \phi(2^t) = 2^t - 2^{t-1} = 8 $

    $\displaystyle 2^{t-1}(2-1) = 8 \rightarrow t-1=3 $

    so

    $\displaystyle n= 2^4 $
    The above works for when $\displaystyle n=p^a $

    What if $\displaystyle n=p^a q^b $?

    $\displaystyle \phi(n) = p^{a-1}(p-1)q^{b-1}(q-1) $. Now if $\displaystyle p,q\neq2 $ we have then that $\displaystyle p^{a-1}=q^{b-1}=1 \implies a=b=1 $ and WLOG $\displaystyle p-1=4,\; q-1=2 \implies p=5,\; q=3 $.
    Thus $\displaystyle n=15 $.

    WLOG if $\displaystyle p=2 $, then $\displaystyle \phi(n) = 2^{a-1}q^{b-1}(q-1) $. This means again that $\displaystyle q^{b-1} = 1\implies b=1 $. So we could have $\displaystyle q-1=2,\; 2^{a-1} = 4 $ or $\displaystyle q-1=4,\; 2^{a-1}=2 $. Or in other words $\displaystyle q=3,\;a=3 $ or $\displaystyle q=5,\; a=2 $.
    Thus $\displaystyle n=24 \text{ or } n=20 $

    What if $\displaystyle n=2p^aq^b $? I'll let you do this one (hint: what's $\displaystyle \phi(n) $?). The answer comes out to be $\displaystyle n=30 $.

    Now what about other $\displaystyle n $? Well, it turns out that with three or more prime divisors, there are just too many factors in $\displaystyle \phi(n) $ i.e. $\displaystyle p_1-1,p_2-1,p_3-1,\cdots $ will all be even and distinct, thus making $\displaystyle \phi(n)>8 $.


    So here's all $\displaystyle n $ with $\displaystyle \phi(n)=8 $: $\displaystyle n=\{15,16,20,24,30\} $.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler Phi function II
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Dec 27th 2009, 04:33 AM
  2. Euler's phi function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 16th 2008, 05:54 PM
  3. Euler's Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 02:52 PM
  4. euler phi function and others
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Aug 4th 2008, 05:43 PM
  5. Help with euler-phi function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 1st 2007, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum