Daily Archives: August 26, 2025

For a positive integer n, let A_2(n):=\#\{\,1\le k\le n:\ \gcd(k,n)\ \text{is a perfect square}\,\}. Then A_2(n)\;=\;\sum_{d^2\mid n}\varphi\!\left(\frac{n}{d^2}\right) \;=\;\prod_{p^{\alpha}\parallel n}\frac{p^{\alpha+1}-(-1)^{\alpha+1}}{p+1}, where \varphi is Euler’s totient function and the product runs over the prime powers p^\alpha dividing n exactly. Explanation. We are … Continue reading →