How close $f(n)$ is to $\phi(n)^2$ asymptotically?

28 Views Asked by At

Consider the number $f(n)=\#\{(a,b) \mid 1\leq a,b\leq n, (a,n)=(b,n)=1,~\text{gcd}(a-b,n)=1\}.$ It is clear that $f(n) \leq \phi(n)^2.$ Is it it known how close $f(n)$ is to $\phi(n)^2$ asymptotically ?

1

There are 1 best solutions below

0
On BEST ANSWER

Well (unless $n=1$) it is at most $\phi(n)^2-\phi(n)$, since every such pair has $a\neq b$.

This can be an equality, for example if $p$ is prime then $f(p)=(p-1)(p-2)=\phi(p)^2-\phi(p)$.

On the other hand $f(n)=0$ whenever $n$ is even, since any $a,b$ coprime to $n$ must both be odd, meaning that $a-b$ is even and has a common factor with $n$.

So I don't think you can say very much beyond $0\leq f(n)\leq \phi(n)^2-\phi(n)$.