Results 1 to 2 of 2

Math Help - Euler Phi Function - finding all solutions

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    119

    Euler Phi Function - finding all solutions

    I have a question about finding all positive integers n such that

     \phi (n) = m where m is given.

    For example  \phi (n) = 12
    ===========================================

    For this problem or any problem, how do you know that the possible number of solutions are finite and you are not missing any.

    Regarding, to  \phi (n) = 12 , here is how I approached it.

    If p | n, then (p-1) | 12. So, the possible p - 1 =1, 2, 3, 4, 6, 12 since they are factors of 12.

    As a result, the possible values of p = 2, 3, 4, 5, 7, 13 but since p is a prime that leaves only p = 2, 3, 5, 7, 13.

    From here, how would I continue?

    I know that  n = p_{1}^{a_{1}} .... p_{k}^{a_{k}}, then
     \phi (n) = \phi(p_{1}^{a_{1}})...\phi(p_{k}^{a_{k}}) , so would I have to check every 1,2,...,k for each single p's?

    Thank you for reading. Any help is greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    For smallish values of m, like m=12, it is possible to enumerate all the integers n with \phi(n)=m, if you go about it systematically.

    Remember that if n=\prod p^\alpha is the factorisation of n into prime powers, then \phi(n) = \prod p^{\alpha-1}(p-1). So if you want to find the possible values of n with \phi(n)=m, you should start by looking for all the factors of m of the form p^{\alpha-1}(p-1).

    Let's take the example m=12. The factors of 12 that are of that form are

    1 = 2^0(2-1)\quad(so 1 = \phi(2)),
    2 = 3^0(3-1) = 2^1(2-1)\quad(so 2 = \phi(3) = \phi(4)),
    4 = 5^0(5-1)\quad(so 4 = \phi(5)),
    6 = 7^0(7-1) = 3^1(3-1)\quad(so 6 = \phi(7) = \phi(9)),
    12 = 13^0(13-1)\quad(so 12 = \phi(13)).

    The only ways that we can make 12 as a product of these numbers are 12=12 = \phi(13), 12=1\times12 = \phi(2)\phi(13), 12=2\times6 = \phi(3)\phi(7) = \phi(3)\phi(9) = \phi(4)\phi(7) = \phi(4)\phi(9), and 12=1\times2\times6 = \phi(2)\phi(3)\phi(7) = \phi(2)\phi(3)\phi(9).

    Notice that there is no way to write 3 in the form p^{\alpha-1}(p-1), so we cannot make use of the factorisation 12=3\times4. On the other hand, there are two ways to write each of the numbers 2 and 6 in that form, which gives us four ways to make use of the factorisation 12=2\times6. Also, we can slip in a factor 1=\phi(2) to any factorisation that does not already include a term arising from a power of 2, such as 2=\phi(4) (but we can have, for example 12=1\times2\times6 = \phi(2)\phi(3)\phi(7), where the 2 arises from \phi(3) rather than \phi(4)).

    Thus there are eight numbers n with \phi(n)=12, namely 13, 21, 26, 27, 28, 36, 42 and 54.
    Last edited by Opalg; November 3rd 2008 at 12:16 AM. Reason: Wasn't systematic enough – overlooked several cases
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Error Bounds for Euler's Method, finding M and L
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: March 13th 2011, 11:42 AM
  2. Euler's theorem question finding the remainder...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 22nd 2011, 04:55 AM
  3. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 08:29 AM
  4. Euler's Phi Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2009, 05:42 PM
  5. Euler's Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 27th 2008, 03:52 PM

Search Tags


/mathhelpforum @mathhelpforum