2
$\begingroup$

Do there exist any integers $n$ such that Euler's totient function $\phi(n) < n/5$? How should I approach solving this problem?

$\endgroup$
5
$\begingroup$

We know that $$\varphi(n) = n\prod_{p \mid n} \left( 1 - \frac{1}{p} \right),$$ so your question asks whether or not $$ \prod_{p \mid n} \left( 1 - \frac{1}{p} \right) < \frac{1}{5}$$ can ever hold. In fact, the limit of the product of terms of the form $\left( 1 - \frac{1}{p} \right)$ is $0$ (which is equivalent to the fact that the sum of the reciprocals of the primes diverges).

So there are infinitely many numbers $n$ such that $\varphi(n) < n/5$, and in fact infinitely many numbers $n$ such that $\varphi(n) < n/k$ for any $k$. This also makes it easy to see that the smallest number $n$ such that $\varphi(n) < n/k$ will be the product of the first $\ell$ primes for some $\ell$.

Now that we know this, it's easy to check that $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030$, and $\varphi(30030) < 30030/5$. $\diamondsuit$

$\endgroup$
  • $\begingroup$ What is the name of that definition for the totient function? I've never seen it before and my textbook doesn't seem to have it. $\endgroup$ – user2049004 Feb 18 '15 at 0:00
  • 1
    $\begingroup$ @user2049004 This is a statement that comes from the totient function being multiplicative. To prove it, you must show that if $\gcd(m,n) = 1$, then $\varphi(mn) = \varphi(m)\varphi(n)$. There are many ways to do this (which are easily lookupable now that you know the word multiplicative), but it's commonly shown through the Chinese Remainder Theorem. (It can also be shown by hand more naively). Once you have that, you get this formula by evaluating $\varphi(p^k)$ and multiplying the correct prime powers to get $n$. $\endgroup$ – davidlowryduda Feb 18 '15 at 0:08

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.