Are there any known methods for finding Upper/Lower bounds on the number of Totients of x less than another number y?

33 Views Asked by At

I guess something like Euler's Totient Function that takes two variables.

Essentially I am trying to figure out a way to bind the number of integers that are Coprime to x that are less than y, where y may be greater or smaller than x.

Thanks in advance!

1

There are 1 best solutions below

1
On

There are some cases in which we can get the exact value of such a function. Define $$\varphi(x,y)=\sum_{\substack{(k,x)=1\\k\le y}}1$$

If $n$ is a positive integer, then $\varphi(x,nx)=n\varphi(x)$. Note that $k$ is coprime with $x$ if and only if $k+x$ is.

If $x\ge 4$ is even, then $x/2$ is not coprime with $x$, and $k$ is coprime with $x$ if and only if $x-k$ is, so $$\varphi\left(x,\frac x2\right)=\frac12\varphi(x)$$

With a similar argument we get this formula for odd $x\ge 3$: $$\varphi\left(x,\frac {x-1}2\right)=\frac12\varphi(x)$$

For $x\le 2$ it is obvious that $$\varphi(1,y)=y$$ $$\varphi(2,y)=\left\lceil\frac y2\right\rceil$$