3 added 388 characters in body

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).

2 correction

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)=x-\sum_i\frac x{p_i}+\sum_{i \Phi(n)=n-\sum_i\frac n{p_i}+\sum_{i \lt j}\frac x{p_ip_j}-\cdots+(-1)^{k}\frac x{n}=xr$$ 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. 1 # Bound the error in estimating a relative totient function 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)=x-\sum_i\frac x{p_i}+\sum_{i \lt j}\frac x{p_ip_j}-\cdots+(-1)^{k}\frac x{n}=xr$$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.$