# Number Theory: Euler's Phi Function

1. Mar 3, 2007

### mattmns

Here is the question from the book:
------------
Determine all n for which $\phi(n) = n -2$.
------------

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 $\phi(p) = p-1$ for all primes p.

Some things we know:

If (m,n)=1, then $\phi(mn) = \phi(m)\phi(n)$.

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

$$\phi(m) = \prod_{i=1}^k \left(1- \frac{1}{p_i}\right)$$

Any hints/ideas? Thanks!

2. Mar 3, 2007

### StatusX

That should be:

$$\phi(m) = m \prod_{i=1}^k \left(1- \frac{1}{p_i}\right)$$

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?

3. Mar 3, 2007

### mattmns

You would get an even larger upper bound, and it would be closer to m.

So if m is composite, then we would have:

$$\phi(m) \leq m\left( 1 - \frac{1}{2} \right)$$

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

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

Thanks.

edit.. OK that seems good, thanks for the hint

Last edited: Mar 3, 2007
4. Mar 3, 2007

### tim_lou

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.

5. Mar 3, 2007

### mattmns

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
6. Mar 3, 2007

### tim_lou

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.

7. Mar 3, 2007

### tim_lou

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
8. Mar 4, 2007

### StatusX

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:

$$2 \geq \frac{m}{p_i}$$

9. Mar 4, 2007

### mattmns

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 $\phi(m)=m-2$

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

Now we have:

$$\phi(m) \leq m\left( 1 - \frac{1}{p_1} \right)$$

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

This means that $a_i = 0 \ \forall i > 1$ since $p_i > p_1 \geq 2 \ \forall i > 1$. And thus we also have that $p_1 = 2$ and that $a_1 - 1 = 1$ (otherwise (if $a_1 - 1 =0$) we would have m = 2), thus m = 4.

Last edited: Mar 4, 2007
10. Mar 4, 2007

### tim_lou

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.

11. Aug 19, 2011

### mdg583

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

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

Rearrange:

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