= Solution
The <inclusion-exclusion principle> says that the size of a finite union is the alternating sum of the sizes of all nonempty intersections of its constituent sets.
For each <prime number> $p\mid n$, let $A_p$ consist of the tuples for which $p$ divides every $x_i$. Exactly $(n/p)^r$ tuples lie in $A_p$, and for distinct primes $p_1,\ldots,p_j\mid n$, exactly $(n/(p_1\cdots p_j))^r$ lie in their intersection. A tuple has greatest common divisor greater than one with $n$ exactly when it belongs to some $A_p$. Inclusion-exclusion therefore gives the <Jordan totient function>
$$
\phi_r(n)
=n^r\sum_{S\subseteq\{p:p\mid n\}}(-1)^{|S|}\prod_{p\in S}p^{-r}
=\boxed{n^r\prod_{p\mid n}(1-p^{-r})}.
$$
Back to article page
