0

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!

user2141965
  • 41

1 Answers1

0

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$$

ajotatxe
  • 65,084
  • Right, I should have mentioned for x, y such that x is not a multiple of y, nor is y a multiple of x, otherwise the answer is pretty trivial, but thank you for putting that all out – user2141965 Jan 22 '18 at 18:27