Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've seen before the general bound $\phi(n) \leq n - n^{1/2}$ for composite $n$. Can this bound be improved at least for those $n$ when we don't have equality above? Say could we possibly have at least $\phi(n) \leq n - kn^{1/2}$ for some $k > 1$?

share|improve this question

3 Answers 3

up vote 4 down vote accepted

Let $n=p^2$. Then $\varphi(n)=p^2-p=n-\sqrt{n}$. So we have equality for infinitely many $n$.

If $n=p^e$ where $e\gt 2$, then $\varphi(n)=p^e-p^{e-1}=n-n^{1-1/e}$. Worst case is $e=3$, $p=2$. In this case we have $n^{2/3}\ge kn^{1/2}$ where $k=2^{1/6}$. Thus $\varphi(n)\le n-2^{1/6}n^{1/2}$.

If $n=ab$ where $a$ and $b$ are greater than $1$ and relatively prime, then $\varphi(n)=\varphi(ab)\le (a-1)(b-1)=n-(a+b)+1$. Note that $a+b\gt 2\sqrt{n}$, so we get $\varphi(n)\le n-2\sqrt{n}+1$ in this case.

share|improve this answer
    
Thanks André Nicolas. How about the case when n is a composite Mersenne number? I remember seeing somewhere that $n \mid \phi(2^n-1)$. –  user152634 Aug 14 at 4:57
    
You are welcome. The bounds we have given cover all composite numbers. They show that in particular we can take $k=2^{1/6}$ for all composite $n$ that are not the square of a prime. Maybe one can do much better for Mersenne composites. Certainly the $k$ can be improved to $2$. –  André Nicolas Aug 14 at 5:02
    
I opened the new question regarding Mersennes. math.stackexchange.com/questions/896937/… Hopefully something nice comes up. Thanks again! –  user152634 Aug 14 at 5:05

We have the formula $$ \phi(n)=n\prod_{\substack{p\mid n\\p\text{ prime}}}\left(1-\frac1p\right)\tag{1} $$ For a composite $n$, the smallest prime $p_0\mid n$ is at most $\sqrt{n}$, so $(1)$ implies $$ \begin{align} \phi(n) &\le n\left(1-\frac1{p_0}\right)\\ &\le n\left(1-\frac1{\sqrt{n}}\right)\\ &=n-\sqrt{n}\tag{2} \end{align} $$ Furthermore, for $n=p^2$, $$ \phi(p^2)=p^2-p\tag{3} $$ Thus, we can find an arbitrarily large composite $n$ so that $\phi(n)=n-\sqrt{n}$.

If we don't have equality as in $(3)$, we have either $n=p^k$ or $n$ has two distinct prime factors. $$ \phi(p^k)=p^k-p^{k-1}\tag{4} $$ Thus, for $k\ge3$ $$ \frac{n-\phi(n)}{\sqrt{n}}=\frac{p^{k-1}}{p^{k/2}}=p^{k/2-1}=n^{1/2-1/k}\ge n^{1/6}\tag{5} $$ so if we are looking for the smallest $\frac{n-\phi(n)}{\sqrt{n}}$, we need to look at $n=pq$. We get $$ \frac{pq-\phi(pq)}{\sqrt{pq}}=\frac{p+q-1}{\sqrt{pq}}=\frac{\sqrt{p}}{\sqrt{q}}+\frac{\sqrt{q}}{\sqrt{p}}-\frac1{\sqrt{pq}}\tag{6} $$ Since $x+\frac1x=2+\left(\sqrt{x}-\frac1{\sqrt{x}}\right)^2\ge2$, with equality only when $x=1$, we have that if $n$ has two distinct prime factors, $$ \frac{n-\phi(n)}{\sqrt{n}}\gt2-\frac1{\sqrt{n}}\implies\phi(n)\lt n-2\sqrt{n}+1\tag{7} $$ Furthermore, inequality $(5)$ guarantees that inequality $(7)$ holds if $n\ge39$ and $n$ is not a prime or the square of a prime.


Checking the integers less than $39$, we see that if $n$ is not a prime or the square of a prime and $n\ne8$ and $n\ne27$, then $(7)$ holds.

share|improve this answer

Well, if $n$ is the product of consecutive primes you get $\phi(n) > n - 2 \sqrt n,$ but it gets close, and you can probably take your $k = 1.5$ for $n>8$ say

2   16 = 2^4
1.999437280176435   1333 = 31 * 43
1.999118949876075   7663 = 79 * 97
1.99871723147485   8383 = 83 * 101
1.998342529102684   2867 = 47 * 61
1.99824032638073   9523 = 89 * 107
1.998065959315103   5561 = 67 * 83
1.997420223212713   6497 = 73 * 89
1.996970389115528   3551 = 53 * 67
1.996107193636781   4307 = 59 * 73
1.99504678865167   2173 = 41 * 53
1.994932096041783   8051 = 83 * 97
1.994893666788084   9167 = 89 * 103
1.993950461300493   2773 = 47 * 59
1.993453519963639   8989 = 89 * 101
1.993124970314336   4189 = 59 * 71
1.993082580330997   4453 = 61 * 73
1.993073020359085   5893 = 71 * 83
1.993044773767945   5293 = 67 * 79
1.991741189771645   91 = 7 * 13
1.991626618969993   7031 = 79 * 89
1.991524132758911   1271 = 31 * 41
1.991274911100793   6059 = 73 * 83
1.991089847651314   8633 = 89 * 97
1.990896104916204   9991 = 97 * 103
1.990568850865158   4331 = 61 * 71
1.990344721501349   1739 = 37 * 47
1.990305174632736   9797 = 97 * 101
1.989992514114262   2279 = 43 * 53
1.989582997411111   7387 = 83 * 89
1.989498190165494   5609 = 71 * 79
1.988391837175112   5767 = 73 * 79
1.988260497982835   6557 = 79 * 83
1.988138364484967   3953 = 59 * 67
1.987540416848836   4891 = 67 * 73
1.987355637820889   3233 = 53 * 61
1.986558698771642   4087 = 61 * 67
1.986341843827027   4757 = 67 * 71
1.986302700472586   5183 = 71 * 73
1.984993267773272   3127 = 53 * 59
1.984865598623816   713 = 23 * 31
1.984328160336157   1073 = 29 * 37
1.983608853697701   3599 = 59 * 61
1.983573651759631   2491 = 47 * 53
1.981884747156589   1927 = 41 * 47
1.980578231727406   1591 = 37 * 43
1.979734037185575   2021 = 43 * 47
1.9783042944476   1147 = 31 * 37
1.976960238957923   1517 = 37 * 41
1.976750859152595   1763 = 41 * 43
1.974727886289034   667 = 23 * 29
1.974435545143253   187 = 11 * 17
1.972482765224911   247 = 13 * 19
1.972314775954277   391 = 17 * 23
1.967760170596957   899 = 29 * 31
1.963961012123931   21 = 3 * 7
1.961295980263253   437 = 19 * 23
1.950751102589306   221 = 13 * 17
1.9474520942613   323 = 17 * 19
1.937329799813845   77 = 7 * 11
1.923356623016309   143 = 11 * 13
1.897366596101028   10 = 2 * 5
1.859339360402736   35 = 5 * 7
1.807392228230128   15 = 3 * 5
1.732050807568877   27 = 3^3
1.632993161855452   6 = 2 * 3
1.414213562373095   8 = 2^3
jagy@phobeusjunior:~$ 
    jagy@phobeusjunior:~$ 
share|improve this answer
    
Thanks. Nice data :) –  user152634 Aug 14 at 5:11
    
My answer says that if $n$ has two distinct prime factors, $$\phi(n)\le n-2\sqrt{n}+1$$ supporting your data. Furthermore, the preceding inequality also holds if $n\ne8$ and $n\ne27$ and $n$ is not a prime or the square of a prime. –  robjohn Aug 14 at 6:06
    
@robjohn, I like your (7) for $n$ at least two distinct prime factors, my left hand column larger then $2 - 1/ \sqrt n$ –  Will Jagy Aug 14 at 20:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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