1. ## Phi Function

Hi everyone,

So i have the following question....

Determine all integers n for which φ(n) is a divisor of n.

Thinking about it logically, I think that the answer is going to be all the powers of 2?

I cant really work out how to set this in some kind of proof/definitive form?

Any ideas?

Thanks

2. ## Re: Phi function

Well, $\varphi(6)=2$ divides 6, so there are also solutions other than powers of 2.

3. ## Re: Phi Function

I know phi(m) has m - 1 relative primes if 'm' is prime, but thats the only pattern I saw. Hope that helps.

4. ## Re: Phi Function

A way to prove that $\phi (2^n) | 2^n$ is by using the following property of the Euler function :

$\phi (p^k) = p^k (1-\frac{1}{p})$

for all primes p and where k>1.
Now note that 2 is prime, so that

$\phi (2^n) = 2^n (1-\frac{1}{2}) = 2^{n-1}$.
This number is a divisor of $2^n$.

I don't know yet how to find other numbers satisfying that property...

EDIT:
You can use the identity

$\phi(n) =n \prod_{p|n} (1-\frac{1}{p}$.

If the only prime divisor of n is 2, then clearly $\phi(n) = n/2$ which is a divisor of n.
Similarly, if the prime divisors of n are just 2 and 3, so $n=2^k 3^l$ where k is nonzero, then
$\phi(n)=n\cdot \frac{1}{2}\cdot \frac{2}{3} = n/3$.

This argument does not seem to work when using other primes, but I'm not sure

5. ## Re: Phi Function

Ah, I've almost figured it out.
Let's try and prove it:

$\phi (n) |n \Leftrightarrow n=2^a 3^b$ with $a\geq 1 , b\geq 0$.

The implication from right to left is easy: I've sort of shown it above already.

For the other implication, note that $\phi(n)$ is even for $n>2$.
Hence, since $\phi(n) | n$, n must be even, so write $n=2^a R$ where $R\geq 1$ is odd.

Now note $\phi(n) = 2^{a-1} \phi(R)$ using multiplicativity of $\phi$. Hence we have

$2^{a-1} \phi(R) | 2^a R \Leftrightarrow \phi(R)|2R$.

Write R as product of primes
$R = p_1^{k_1} \cdots p_r^{k_r}$. Then we have
$p_1^{k_1-1}(p_1-1) \cdots p_r^{k_r} | 2p_1^{k_1}\cdots p_r^{k_r}$

Hence
$(p_1-1)(p_2-1)...(p_r-1)|2p_1 p_2 \cdots p_r$.

Now assume that $r=1$ to find
$p_1-1 | 2p_1$. This implies $p_1 = 3$ and thus $n=2^a 3^b$ for some b greater than or equal to zero.

I'm not sure why we have that r=1. This remains to be proven, but I'm pretty sure this is the idea.