0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user2141965 Jan 22 '18 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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