3
$\begingroup$

I need to find all the integers such that $\phi (n) \mid n $, where $\phi$ is the totient function.

Using $$\phi(n)=n\prod(1-1/p)$$where the product runs over all prime factors of n, one gets that $$n/\phi(n)=\prod\frac{p}{p-1}$$ and this needs to be an integer. This is true if the list of primes is just {2} or {2,3}. I don't think there are other solutions, but I am having trouble showing it.

$\endgroup$
2
$\begingroup$

Hint:

If $n$ has two (or more) odd prime factors, you will have at least two factors of $2$ in the denominator of your product, but they can't both be cancelled since the only possible even prime (in the numerator) is $2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.