= Jordan's totient function
{c}
{title2=$J_k(n)$}
{wiki}
= Jordan totient function
{c}
{synonym}
For <positive integers> $k,n$, <Jordan's totient function> $J_k(n)$ counts <tuples> $(a_1,\ldots,a_k)$ of <residue classes> <modulo> $n$ for which $\gcd(a_1,\ldots,a_k,n)=1$. The coordinates together must avoid a common <prime divisor> of $n$; they need not each be <units>.
For each <prime factor> $p$ of $n$, exactly $(n/p)^k$ tuples have all coordinates divisible by $p$. The <inclusion-exclusion principle>, applied to simultaneous divisibility by the distinct <prime factors>, therefore gives
$$
J_k(n)=n^k\prod_{p\mid n}(1-p^{-k}).
$$
In particular $J_1(n)=\varphi(n)$ is <Euler's totient function>. For $k=2,n=6$, the formula gives $J_2(6)=36(1-1/4)(1-1/9)=24$. The pair $(2,3)$ is counted because $\gcd(2,3,6)=1$, even though neither coordinate is <coprime> to six.
Back to article page
