# How to count the number of perfect square greater than $N$ and less than $N^2$ that are relatively prime to $N$?

I know a little about Euler's totient function that counts integer less than $N$ that are relatively prime to $N$.

But I don't know how to modify the function for perfect square numbers, or maybe there is another formula I don't know about.

Can somebody provide any help? Thanks a lot.

We may assume that $$N=\prod_{l=1}^{k} p_l^{\alpha_l}$$ is the factorization of $N$ and define $\square_N(m)$ as the number of squares $\leq m$ that are coprime with $N$. For our purposes it is enough to compute $\square_N(N^2)-\square_N(N)$, where $\square_N(m)$ accounts for the integers in the range $[1,\sqrt{m}]$ that are coprime with $p_1,p_2,\ldots,p_k$. By the inclusion-exclusion principle $\square_N(m)$ is expected to behave like $$\sqrt{m}\prod_{l=1}^{k}\left(1-\frac{1}{p_l}\right)$$ plus a small error term, hence $\square_N(N^2)-\square_N(N)$ is expected to behave like $$N\prod_{l=1}^{k}\left(1-\frac{1}{p_l}\right) +O(\sqrt{N}) = \varphi(N)+O(\sqrt{N}).$$