Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory: Euler's Phi Function

  1. Mar 3, 2007 #1
    Here is the question from the book:
    Determine all n for which [itex]\phi(n) = n -2[/itex].

    Now it seems that the only time this will work is for n = 4. However, I haven't any idea of how to prove (or justify) this. I have thought about working primes and composites, since we know [itex]\phi(p) = p-1[/itex] for all primes p.

    Some things we know:

    If (m,n)=1, then [itex]\phi(mn) = \phi(m)\phi(n)[/itex].

    If [itex]m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}[/itex] is the prime factorization of m, then:

    [tex]\phi(m) = \prod_{i=1}^k \left(1- \frac{1}{p_i}\right)[/tex]

    Any hints/ideas? Thanks!
  2. jcsd
  3. Mar 3, 2007 #2


    User Avatar
    Homework Helper

    That should be:

    [tex]\phi(m) = m \prod_{i=1}^k \left(1- \frac{1}{p_i}\right)[/tex]

    Note that each of those factors in the product is less than one, so if you drop any of them, you get an upper bound for phi(m). What happens if you drop all but one?
  4. Mar 3, 2007 #3
    You would get an even larger upper bound, and it would be closer to m.

    So if m is composite, then we would have:

    [tex]\phi(m) \leq m\left( 1 - \frac{1}{2} \right)[/tex]

    and that would be as large as phi(m) could get.

    So then if we have [itex]\phi(m) = m - 2[/itex] we then get [itex]m-2 \leq m(1-1/2) \Rightarrow m \leq 4 \Rightarrow m = 4[/itex] (since m > 0 and m is a composite natural number).


    edit.. OK that seems good, thanks for the hint :smile:
    Last edited: Mar 3, 2007
  5. Mar 3, 2007 #4
    hmm, I don't think that is correct, consider, m=7*9, phi(m)=6*8=48 which is certainly greater than 7*9/2. the inequality should be
    phi(m)<=m, which doesn't really help the problem.
  6. Mar 3, 2007 #5
    Yes, you are correct, hmm, I should have it the other way around. Instead of 1/2 I should have 1 over the smallest prime in the decomposition of m.
    Last edited: Mar 4, 2007
  7. Mar 3, 2007 #6
    I don't think the inequality helps at all, m is canceled and you get nothing ...I am also clueless... this looks like an interesting problem though.
  8. Mar 3, 2007 #7
    hmm... I guess one shouldn't tackle this problem algebraically. Let's put things in words.

    What integer has the property that all integers less than it except two of them are relatively prime to itself? The answer should now be clear.
    Last edited: Mar 3, 2007
  9. Mar 4, 2007 #8


    User Avatar
    Homework Helper

    No, the inequality helps, you just need to pick one of the prime factors of m (ie, not 2 unless that divides m). And m doesn't cancel, you end up with:

    [tex]2 \geq \frac{m}{p_i} [/tex]
  10. Mar 4, 2007 #9
    Hmm, I am really not seeing how that makes it clear, care to explain a little?

    Thanks StatusX I think I have it now.


    Suppose [itex]\phi(m)=m-2[/itex]

    Certainly m cannot be prime, so let [itex] m = p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}[/itex] be a composite number with [itex]p_1 < p_2 < \cdots < p_r[/itex].

    Now we have:

    [tex]\phi(m) \leq m\left( 1 - \frac{1}{p_1} \right)[/tex]

    Since [itex]\phi(m) = m - 2[/itex] we get [tex]2 \geq \frac{m}{p_1} = p_1^{a_1 - 1}p_2^{a_2}\cdots p_r^{a_r}[/tex]

    This means that [itex]a_i = 0 \ \forall i > 1[/itex] since [itex]p_i > p_1 \geq 2 \ \forall i > 1[/itex]. And thus we also have that [itex]p_1 = 2[/itex] and that [itex]a_1 - 1 = 1[/itex] (otherwise (if [itex]a_1 - 1 =0[/itex]) we would have m = 2), thus m = 4.
    Last edited: Mar 4, 2007
  11. Mar 4, 2007 #10
    yeah, you are correct, the answer is indeed four. because a number that is relatively prime to all but two numbers must have only 2 prime factors, otherwise at least three numbers will have common factor with n. n=ab, one can show that a must be 2, since otherwise, b, 2b, and 3b... have common factors with n. by symmetry, b=2, n=4. I guess the inequality is another nice way of doing it.
  12. Aug 19, 2011 #11
    How about this:

    Write n in the form n=kpa, where p[STRIKE]|[/STRIKE]k.

    Then ϕ(kpa) = ϕ(k)ϕ(pa) = ϕ(k)pa-1(p-1) = kpa - 2


    pa-1(p(k-ϕ(k)) + ϕ(k)) = 2

    Notice, k-ϕ(k) is a positive integer, so p(k-ϕ(k)) + ϕ(k) is a positive integer.

    Letting (p(k-ϕ(k)) + ϕ(k))=j, we have
    pa-1j = 2

    If j=2, a = 1:
    p(k-ϕ(k)) + ϕ(k) = 2, k > ϕ(k), ϕ(1) = 1 (I think?) so k>2 is impossible, k=2 => p=1 impossible, k<2 impossible.

    So, j = 1, a = 2, p = 2
    2(k-ϕ(k)) + ϕ(k) = 1 implies k=1, ϕ(k)=1

    This gives the only answer, n=1*22 = 4
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook