$\phi(n)$ being Euler's totient function.

Regarding effort put into the problem:

In the case that $n$ is a prime $p$, then it is given that $\phi(p) = p-1$. It is also given that $n\ne 2$, so the fact that $p-1 \ge \sqrt p$, or $(p-1)^2 \ge p$ is easy enough to prove in it of itself.

Considering the case were $n$ is some non-prime number, then $n$ may be written as its power prime factorization $n=p^{a_1}_1p^{a_2}_2 \ldots p^{a_k}_k$. It is given that $\phi$ is multiplicative, so applying this to the original problem we have $\phi(n)=\phi(p^{a_1}_1) \phi(p^{a_2}_2) \ldots \phi(p^{a_k}_k)$.

It is given that $\phi(p^{a_j}_j)=p^j_j-p^{a_j-1}_j=p^{a_j}_j(1-\frac{1}{p_j})$, so the above can be rewritten as

$\phi(n)=p^{a_1}_1p^{a_2}_2 \ldots p^{a_k}_k(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2}) \ldots (1-\frac{1}{p_k})$.

Which is where I am stuck, as I don't quite see how to prove that the above product (or product squared) is greater than $\sqrt n$ (or $n$ in the product squared case). Is this the wrong angle to be approaching the problem from, or are one of my inferences altogether mistaken?

  • 1
    $\begingroup$ Your inferences are correct. $\phi(n) = n \times \Pi \left(1-\frac{1}{p}\right)$ is well known. I doubt you would need to show a proof as you have shown here. Maybe an interesting question to ask would be why this doesn't hold for $2$ and $6$. What's special about these? $\endgroup$ – Guy Mar 22 '14 at 20:39
  • $\begingroup$ Let's try to make the statement false. Let's try to find all such "Euler unfriendly" numbers. Which ones should we be looking at? As an example, of the two, which is more likely to be Euler unfriendly: $7 \times 11$ or $3 \times 5$? What about $2 \times 3$ or $2^2 \times 3$? $\endgroup$ – MCT Mar 22 '14 at 21:08
  • 1
    $\begingroup$ $\phi(n)$ is fully multiplcative in the usual number theoritic sense, so we just need to consider the $n=p^k$ case. Can you take it from here? $\endgroup$ – chubakueno Mar 22 '14 at 21:33

Sorry for this being very non-rigorous and not very elegant either.. as a high schooler I don't know many "high powered" tools that I could use to solve this.

Let's try to find $n$ which don't fit the statement.

Proposition: We'll get our best bet at falsifying the statement among primorials, i.e., those numbers of the form $\displaystyle \prod_{n = 1}^k p_n$

Consider when it is not a primorial.

Case 1: We add a $p_i$ to our primorial $p_k \#$ with $i < k$. In other words, $n$ has a repeated factor. Then $p_i \phi(n) = \phi (np_i)$. Thus, by doing this we increase the left hand side by $p_i$ while increasing our right hand side only by $\sqrt p_i$, so this is unproductive. Conclusion, we have at most of one of any prime factor in $n$.

Case 2: What if we didn't take the smallest primes. What if we changed a factor $p_i$ in $p_k \#$ into a $p_j$ with $i < k <j$? Then we would increase the left hand side by a factor of $(\frac{p_j}{p_i})(\frac{p_i}{p_i-1})(\frac{p_j-1}{p_j})$ while increasing the left hand side by a lesser factor of $\sqrt{\frac{p_j}{p_i}}$. Conclusion, we take the smallest primes we can.

Furthermore, once we find one primorial that works for the statement, all further primorials work as well. Consider if $p_i \#$ doesn't work, i.e. $\phi(p_i \#) \geq \sqrt{p_i \#}$. Then $\phi (p_{i+1} \#) = \phi(p_{i+1})\phi(p_i \#) \geq \sqrt{p_{i+1}} \sqrt{p_i \#}$, since $\phi(p_{i+1}) = p_{i+1} - 1 \geq \sqrt{p_{i+1}}$ for all $i \geq 1$

So, by inspection we find $n = 2, n = 6$ don't work. $n = 24$ works because $6 \geq \sqrt{24}$, so no further primorials work either.

To finish, we just need to do some inspection in $n =2$ and $n = 6$ to make sure that variations of them work. For $n = 2$, we check $2^2$, and find that $\phi (4) = 2 \geq 2$ works. For $n = 6$, we check $2^2 \times 3$ and $2 \times 3^2$, and find that both of them work. Thus, $n = 2, n = 6$ are the only integers $n$ which do not satisfy the statement.


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.