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 counting residues k\bmod n whose gcd with n is a square divisor of n. The first expression partitions by the value of that gcd; the second turns that partition into a tidy multiplicative closed form.

Proof

Partition by the gcd. If s\mid n is a perfect square, then the solutions to \gcd(k,n)=s are exactly the numbers k\equiv s\,t\pmod n with \gcd(t,n/s)=1. There are \varphi(n/s) such residue classes. Summing over all square divisors s gives A_2(n)=\sum_{\substack{s\mid n\\ s\ \text{square}}}\varphi\!\left(\frac{n}{s}\right) =\sum_{d^2\mid n}\varphi\!\left(\frac{n}{d^2}\right), after writing s=d^2. Multiplicativity and evaluation on prime powers. Both the condition “d^2\mid n” and \varphi are multiplicative, so A_2 is multiplicative. It suffices to compute A_2(p^\alpha).

If \alpha=2m+1 is odd, the square divisors are p^{0},p^{2},\dots,p^{2m}, so A_2(p^{2m+1})=\sum_{j=0}^{m}\varphi\bigl(p^{2m+1-2j}\bigr) =(p-1)\sum_{j=0}^{m}p^{2m-2j} =\frac{p^{2m+2}-1}{p+1}=\frac{p^{\alpha+1}-1}{p+1}. If \alpha=2m is even, the square divisors are p^{0},p^{2},\dots,p^{2m}, so A_2(p^{2m})=\sum_{j=0}^{m}\varphi\bigl(p^{2m-2j}\bigr) =\Bigl[(p-1)\sum_{j=1}^{m}p^{2m-2j}\Bigr]+1 =\frac{p^{2m+1}+1}{p+1}=\frac{p^{\alpha+1}+1}{p+1}.

Combining the two cases yields

A_2(p^\alpha)=\frac{p^{\alpha+1}-(-1)^{\alpha+1}}{p+1},

and multiplicativity gives the stated product over all p^\alpha\parallel n. ∎

Quick checks and corollaries

Squarefree n. If n is squarefree, the only square divisor is 1, so A_2(n)=\varphi(n). The product formula gives \prod_{p\mid n}\frac{p^2-1}{p+1}=\prod_{p\mid n}(p-1)=\varphi(n), matching. Prime powers. For n=p: A_2(p)=\frac{p^2-1}{p+1}=p-1 (only gcd =1). For n=p^2: A_2(p^2)=\frac{p^3+1}{p+1}=p^2-p+1 (gcd =1 or p^2). Bounds. For all n\ge 1: \varphi(n)\le A_2(n)<n, with equality on the left iff n is squarefree (as above) and strict inequality on the right for all n>1 because some gcds are non-square. Example. n=12=2^2\cdot 3. The product gives A_2(12)=\frac{2^{3}+1}{2+1}\cdot\frac{3^{2}-1}{3+1}=\frac{9}{3}\cdot\frac{8}{4}=3\cdot 2=6. Indeed, among 1,\dots,12, the k with \gcd(k,12)\in\{1,4\} are \{1,5,7,11\} (four with gcd 1) and \{4,8\} (two with gcd 4).

Generalization (gcd a perfect t-th power)

Fix t\ge 1. Define

A_t(n):=\#\{\,1\le k\le n:\ \gcd(k,n)\ \text{is a perfect }t\text{th power}\,\}.

Then

A_t(n)=\sum_{d^t\mid n}\varphi\!\left(\frac{n}{d^t}\right),

and A_t is multiplicative. For a prime power n=p^\alpha, write \alpha=tm+r with 0\le r\le t-1. Then

A_t(p^\alpha)= \begin{cases} \displaystyle p^{\,r-1}\,\frac{(p^{\alpha-r+t}-1)(p-1)}{p^t-1}, & r>0,\\[1.0em] \displaystyle p^{\,t-1}\,\frac{(p^{\alpha}-1)(p-1)}{p^t-1}+1, & r=0. \end{cases}

(One obtains this by the same gcd-partition and a geometric-series sum; the t=2 case collapses to the earlier closed forms.)

A convenient Dirichlet-series packaging is:

\sum_{n\ge1}\frac{A_t(n)}{n^s}\;=\;\Bigl(\sum_{n\ge1}\frac{\varphi(n)}{n^s}\Bigr)\Bigl(\sum_{n\ge1}\frac{\mathbf{1}_{\text{$t$th power}}(n)}{n^s}\Bigr) =\frac{\zeta(s-1)}{\zeta(s)}\cdot \zeta(ts),

which makes multiplicativity and many average-order questions transparent.

Sanity checks. t=1 gives A_1(n)=\sum_{d\mid n}\varphi(d)=n (every gcd is a 1st power). t=3, n=72=2^3\cdot 3^2:

For 2^3 (here r=0): A_3(2^3)=2^{2}\frac{(2^{3}-1)(1)}{2^3-1}+1=4+1=5. For 3^2 (here r=2): A_3(3^2)=3^{1}\frac{(3^{3}-1)(2)}{3^3-1}=3\cdot 2=6. So A_3(72)=5\cdot 6=30. Indeed, the admissible gcds are 1 and 8; there are \varphi(72)=24 with gcd 1 and \varphi(9)=6 with gcd 8.

Why this is interesting

It’s a crisp “gcd-filtered totient” identity with a surprisingly compact Euler-product factorization. The general t-version offers a family of arithmetic functions A_t with a simple Dirichlet series \zeta(ts)\zeta(s-1)/\zeta(s), inviting further study (mean values, extremal behavior, etc.). It gives immediate, exact counts for concrete modular questions: “how many residues mod n have gcd with n equal to a square/cube/etc.?”