2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Taufan Silitonga Jul 11 '16 at 3:57
  • $\begingroup$ 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 $\endgroup$ – Taufan Silitonga Jul 11 '16 at 4:04

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.