Number Theory: Euler's Phi Function

[mattmns]

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!

 

[StatusX]

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?

 

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

[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).

Thanks.

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

 

[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.

 

[mattmns]

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.

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.

 

[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.

 

[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.

 

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

[tex]2 \geq \frac{m}{p_i} [/tex]

 

[mattmns]

The answer should now be clear.

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.

 

[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.

 

[mdg583]

How about this:

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

Then ϕ(kp^a) = ϕ(k)ϕ(p^a) = ϕ(k)p^a-1(p-1) = kp^a - 2

Rearrange:

p^a-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
p^a-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*2² = 4