Let $n=p_1^{e_1}\cdots p_k^{e_k}$ be an integer with $k$ prime factors. We know that the number of integers less than $n$ and coprime to it is
$$\Phi(n)=n-\sum_i\frac n{p_i}+\sum_{i \lt j}\frac n{p_ip_j}-\cdots+(-1)^{k}\frac n{n}=nr$$ where $r=\prod(1-\frac 1{p_i})$.

For any positive integer $x$, the number of integers less than or equal to $x$ and relatively prime to $n$ is given exactly by the alternating sum $$\Phi(n,x)=x-\sum_i\lfloor{x/{p_i}}\rfloor+\sum_{i \lt j}\lfloor x/{p_ip_j}\rfloor-\cdots+(-1)^{k}\lfloor x/{n}\rfloor$$

How large and how small can the error $\Phi(n,x)-xr$ be? Can the absolute value of the error exceed $k$?

Certainly the error can be no more (in absolute value) than $2^k$, probably it is easy to show that it could not be more than the middle binomial coefficient $\binom k{\lfloor k/2 \rfloor}$. I can see that it could get (almost) as large as $ k $ by imitating the following example:

The integers $1122659, 2245319, 4490639, 8981279, 17962559, 35925119, 71850239$ are a Cunningham chain as is $2,5,11,23,47$ in that each member is prime and one more than twice the previous one. If $n$ is the product of the $7$ primes from the first chain and $x=1122659\cdot64-1=71850175$ then all seven terms $ x/{p_i} $ are just a bit less than an integer so, without the rounding down to an integer, the estimate $rx$ will too small by about $7$ (the other terms are quite small). Of course it is not known for sure that there are arbitrary length chains. Maybe a similar idea could get an error of order $2k$ or $k^2.$

later Thanks for the answers. I give one of my own below explaining that actually the best we could hope for is $2^{k-1}$ and then exhibiting a construction of D. H. Lehmer which attains $(1-2/q)2^{k-1}$ for arbitrary $q$. This is pretty much a result of the other answers, but I thought it was worth showing off the construction (which is not immediately clear from the article).

  • $\begingroup$ Just to remind you, this is a generalization of the problem you helped me with last year. I was looking at the case of primorials then. It may help in the general case. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2012.02.17 $\endgroup$ Commented Feb 17, 2012 at 22:11
  • $\begingroup$ Also, phi(n) is not xr unless x=n. I like the question, but it needs a little polish. Gerhard "Ask Me About System Design" Paseman, 2012.02.17 $\endgroup$ Commented Feb 17, 2012 at 22:13
  • 2
    $\begingroup$ Aaron, in your 1st display, each $x$ should be $n$, right? $\endgroup$ Commented Feb 17, 2012 at 22:19
  • $\begingroup$ Ah yes, the perils of cut and paste. Indeed they should be $n$ and now are. $\endgroup$ Commented Feb 17, 2012 at 22:26
  • $\begingroup$ A slightly smoother way to phrase this: The running total gives a step function starting at $(0,0)$ and ending at $(n,\Phi(n)).$ It takes a jump of $1$ at certain integers. The line connecting the endpoints has slope $r$. Does the running total stay between $rx-k$ and $rx+k$? Viewed as path made of vertical and horizontal segments the graph is centrally symmetric. $\endgroup$ Commented Feb 17, 2012 at 23:26

3 Answers 3


First of all as you remark above, it is easy to see by elementary means that the error is at most $2^k$. It was an old conjecture of Erdos that this error term could be improved to $o(2^k)$. However this conjecture turns out not to be true!

In 1951 Vijayaraghavan proved that the error term $O(2^k)$ is best possible in the sense that for any $k\in\mathbb{N}$ and $\delta >0$ you can find an integer $n$ with exactly $k$ distinct prime factors, and a real number $x$, such that


Vijayaraghavan's paper is On a problem in elementary number theory. J. Indian Math. Soc. 15, (1951).

For a more detailed and up to date discussion you could look at the more recent paper Codecà, Nair, An extension of a result of Lehmer on numbers coprime to n. Ramanujan J. 16 (2008), no. 1, 59–71.

  • $\begingroup$ Do you recall what could be said about such x that gave such a large error, or how many intervals of such x existed for small delta? (I imagine there would be at least k! many.) Gerhard "Ask Me About System Design" Paseman, 2012.02.18 $\endgroup$ Commented Feb 18, 2012 at 16:14
  • $\begingroup$ @Gerhard Paseman No, I'm not sure but that sounds like an interesting question. $\endgroup$ Commented Feb 19, 2012 at 16:09
  • $\begingroup$ At least for the simpler proof of Lehmer the example is pretty explicit. For $n=29\cdot 59 \cdot 89 \cdot 149$ (made of primes of the form $30c-1$ ) it is $x=\frac{n+29}{30}-1.$ I tried to spell this out a bit in an answer below. $\endgroup$ Commented Feb 22, 2012 at 7:52

In fact the absolute value could not be greater than $2^{k-1}.$ Let $\{z\}=z-\lfloor z \rfloor$ denote the fractional part of $z$, then $$\Phi(n,x)-xr=0-\sum_i\{x/{p_i}\}+\sum_{i \lt j}\{ x/{p_ip_j}\}-\cdots+(-1)^{k}\{x/{n}\}$$ is a sum of $2^k$ terms, each between $0$ and $1$, half added and half subtracted. There is no reason to expect the first $k$ primes to give the optimal gap, and in fact they do not. For that matter, the question would be as interesting to me if the $p_i$ are simply relatively prime integers. The references given by Alan Haynes are apt and lead one to look at the article The distribution of totatives by D. H. Lehmer. Even there the key example is a bit hard to work out. If $q$ is any integer and $p_1\lt\dots\lt p_k$ are $k$ primes all of the form $p_i=c_iq-1$ then for $n=p_1p_2\cdots p_k$ there is a number $1 \lt x \lt n$ for which $|\Phi(n,x)-xr| \gt 2^{k-1} \frac{q-2}{q}.$ Let $C=\prod c_i$ It is esy to see that $$n=Cq^k-(\sum_iC/c_i)q^{k-1}+(\sum_{i\lt j}C/c_ic_j)q^{k-2}-\cdots+(-1)^k.$$ A similar expression holds for any product of several of the $p_i.$ The essentially unique extremal $x$ is $$\frac{n +(-1)^kp_1}{q}-1.$$ At this point I will simply illustrate with $k=4.$ Then

$$n=c_{1}c_{2}c_{3}c_{4}{q}^{4}- \left( c_{1}c_{2}c_{3}+c_{1}c_{2}c_{4}+c_{1}c_{3}c_{4}+c_{2}c_{3}c_{4} \right) {q}^{3} $$$$ + \left( c_{1}c_{2}+c_{1}c_{3}+c_{1}c_{4}+c_{2}c_{3}+c_{2}c_{4}+c_{3}c_{4} \right) {q}^{2}- \left( c_{1}+c_{2}+c_{3}+c_{4} \right) q+1$$

and $$x=c_{1}c_{2}c_{3}c_{4}{q}^{3}- \left( c_{1}c_{2}c_{3}+c_{1}c_{2}c_{4}+c_{1}c_{3}c_{4}+c_{2}c_{3}c_{4} \right) {q}^{2} $$$$ + \left( c_{1}c_{2}+c_{1}c_{3}+c_{1}c_{4}+c_{2}c_{3}+c_{2}c_{4}+c_{3}c_{4} \right) {q}- \left( c_{2}+c_{3}+c_{4} \right)-1 $$ So $$x/p_1p_2p_3p_4-\lfloor x/p_1p_2p_3p_4\rfloor =x/n \approx 1/q$$ while, each term $$x/p_i-\lfloor x/p_i\rfloor=1-\frac{c_i-c_1+1}{c_iq-1} \approx 1-1/q $$ and each term $$x/(p_ip_j)-\lfloor x/(p_ip_j)\rfloor=\frac{c_ic_jq-(c_i+c_j)+c_1-1}{c_ic_jq^2-(c_i+c_j)q+1}\approx 1/q.$$ The terms of one sign are very about $1/q$ and those of the other are about $1-1/q.$ this accounts for the entire summation being close to $(1-2/q)2^{k-1}$

The other extreme is at $n-1-x$.


Westzynthius showed that for large k, and n the kth primorial, there were gaps of length greater than p_k g(p_k), where g was some increasing function involving log(p_k) and iterated log of p_k, the kth prime. This implies that there will be horizontal segments of at least that length in the graph Aaron Meyerowitz suggests. I'll do the arithmetic later, but I expect it to lead to an error of something like k log(k) minimum. Using Jacobsthal's function and Iwaniec's estimate, it is likely that the error is bounded by k^2.

Gerhard "Ask Me About System Design" Paseman, 2012.02.17

  • $\begingroup$ Note that one could have a very long horizontal segment and yet stay very close to a sloped line provided that the slope is small. $\endgroup$ Commented Feb 19, 2012 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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