On the number of Hall divisors of an integer A Hall divisor of an integer $n$ is a divisor $d$ of $n$ such that $d$ and $n/d$ are coprime. If $n$ is a positive integer, then $\varphi(n)$ is the number of integers $k$ in the range $1\leq k\leq n$ for which $\gcd(n, k) = 1$. We know that $$\varphi(n)=n\prod_{p|n}(1-\dfrac{1}{p}).$$ Now how can we calculate the number of Hall divisors of an integer $n$?

For any $n$, we can write $n$ as prime factorizations $$ n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k} $$ where $p_i$'s are prime numbers and $e_i\ge 1$ for all $i=1,\dots,k$.

Note that any hall divisor of $n$to be of the form $d=p_1^{f_1}p_2^{f_2}\dots p_k^{f_k}$ where $f_i=0 \textrm{ or } e_i$ since otherwise there will be common prime factor(s) between $d$ and $n/d$.

Since there are $k$ prime numbers for which each of them you have two choice in its power, i.e., $0$ or $e_i$ then there are $2^k$ hall divisors.