Results 1 to 4 of 4

Math Help - Euler Totient problem

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    36

    Euler Totient problem

    Find all n such that:

    \varphi(n)=12
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The \varphi(*) is a multiplicative function so that if m and n are coprime, then...

    \varphi(m\cdot n)= \varphi(m)\cdot \varphi(n) (1)

    For n=1 and n=2 is \varphi(n)=1 and \forall n>2 \varphi(n) is an even number, so that the solutions of the equation...

    \varphi (m\cdot n)=12 (2)

    ... are obtained by systematic search of couples of coprime numbers m and n for which is...

    \varphi(m)=12, \varphi(n)=1

    \varphi(m)=6, \varphi(n)=2 (3)

    Since \varphi(13)=12 solutions are...

    13 \cdot 1 =13

    13\cdot 2 = 26

    Since  \varphi(7)=6 also solutions are...

    7 \cdot 3 = 21

    7 \cdot 4= 28

    7 \cdot 6 = 42

    Finally is \varphi (9)= 6 so that solution is...

    9\cdot 4 = 36

    The numbers k for which is \varphi(k)=12 are...

    k=13,21,26,28,36,42

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    54
    Quote Originally Posted by chisigma View Post
    The \varphi(*) is a multiplicative function so that if m and n are coprime, then...

    \varphi(m\cdot n)= \varphi(m)\cdot \varphi(n) (1)

    For n=1 and n=2 is \varphi(n)=1 and \forall n>2 \varphi(n) is an even number, so that the solutions of the equation...

    \varphi (m\cdot n)=12 (2)

    ... are obtained by systematic search of couples of coprime numbers m and n for which is...

    \varphi(m)=12, \varphi(n)=1

    \varphi(m)=6, \varphi(n)=2 (3)

    Since \varphi(13)=12 solutions are...

    13 \cdot 1 =13

    13\cdot 2 = 26

    Since  \varphi(7)=6 also solutions are...

    7 \cdot 3 = 21

    7 \cdot 4= 28

    7 \cdot 6 = 42

    Finally is \varphi (9)= 6 so that solution is...

    9\cdot 4 = 36

    The numbers k for which is \varphi(k)=12 are...

    k=13,21,26,28,36,42


    \chi \sigma
    Hi, thank you for directing me here. Its good to see an example, but i dont understand this method.

    Why do you multiply 7 by 3, 4 and 6? And how do you get \phi(7) = 6 and \phi(9) = 6. I know you can easily work these out but aren't both of these just an instance of the same sort of question as \phi(m) = 12? Aren't there more \phi(m) = 6?

    Sorry if i'm being a bit slow, all this is very confusing for me.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The basic assumptions are...

    a) is \varphi(n)=1 only for n=1 and n=2. For all  n>2 , \varphi (n) is an even number...

    b) is \varphi(m\cdot k)=\varphi(m)\cdot \varphi(k) if and only if m and k are coprime...

    On the basis of b) the identification of an n for which \varphi(n)=12 is for the fact that must be n=m\cdot k where m and k are coprime and \varphi(m)\cdot \varphi(k) = 12. There are the following possibilities...

    \varphi(m)=12 , \varphi(k)=1

    \varphi(m)=6 , \varphi(k)=2

    The situation...

    \varphi(m)=4 , \varphi(k)=3

    ... as proposed by tonio in the original post, is impossible on the basis of a)...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's totient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 30th 2010, 06:21 PM
  2. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 11th 2009, 04:38 PM
  3. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 12th 2009, 06:11 PM
  4. Euler Totient
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 29th 2009, 09:46 PM
  5. Euler's totient function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 08:53 PM

Search Tags


/mathhelpforum @mathhelpforum