Results 1 to 2 of 2

Thread: 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

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

    For example $\displaystyle \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 $\displaystyle \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 $\displaystyle n = p_{1}^{a_{1}} .... p_{k}^{a_{k}}$, then
    $\displaystyle \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
    10
    For smallish values of m, like m=12, it is possible to enumerate all the integers n with $\displaystyle \phi(n)=m$, if you go about it systematically.

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

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

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

    The only ways that we can make 12 as a product of these numbers are $\displaystyle 12=12 = \phi(13)$, $\displaystyle 12=1\times12 = \phi(2)\phi(13)$, $\displaystyle 12=2\times6 = \phi(3)\phi(7) = \phi(3)\phi(9) = \phi(4)\phi(7) = \phi(4)\phi(9)$, and $\displaystyle 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 $\displaystyle p^{\alpha-1}(p-1)$, so we cannot make use of the factorisation $\displaystyle 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 $\displaystyle 12=2\times6$. Also, we can slip in a factor $\displaystyle 1=\phi(2)$ to any factorisation that does not already include a term arising from a power of 2, such as $\displaystyle 2=\phi(4)$ (but we can have, for example $\displaystyle 12=1\times2\times6 = \phi(2)\phi(3)\phi(7)$, where the 2 arises from $\displaystyle \phi(3)$ rather than $\displaystyle \phi(4)$).

    Thus there are eight numbers n with $\displaystyle \phi(n)=12$, namely 13, 21, 26, 27, 28, 36, 42 and 54.
    Last edited by Opalg; Nov 2nd 2008 at 11:16 PM. 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: Mar 13th 2011, 10:42 AM
  2. Euler's theorem question finding the remainder...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Feb 22nd 2011, 03:55 AM
  3. Euler Function phi(n)
    Posted in the Number Theory Forum
    Replies: 22
    Last Post: May 29th 2010, 07:29 AM
  4. Euler's Phi Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 26th 2009, 04:42 PM
  5. Euler's Function
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 27th 2008, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum