# 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.

## 1 Answer

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}).$$

• thanks a lot for your answer ,, But I am just a beginner and i can't understand your formula well.. can you explain it in general language please? – Taufan Silitonga Jul 11 '16 at 3:57
• this is the problem statement sir.. given a number N, you should count how many perfect square numbers bigger than N and smaller than N^2, which has no prime factor exists in number N factorization (i.e. all of the prime factors do not exist in number N factorization) if N = 10 then the output should 2 (49 & 81) if N = 12 then the output should 3 thanks – Taufan Silitonga Jul 11 '16 at 4:04