Euler's totient function and its inverse (Q1147740)

Let \(n\) be a positive integer and let \(\varphi(n)\) be Euler's totient function. For a given positive integer \(m\) the set \(\varphi^{-1}(m)\) consists of all \(n\) such that \(\varphi(n) = m\). If \(\varphi^{-1}(m)\) is non-empty then it is easy to see that \(\varphi^{-1}(m)\) is bounded below by \(m\) and above by \(m\prod p/(p -1)\) where \(p\) runs over all primes such that \((p-1)\mid m\). In this paper a constructive method is given for finding all of the elements of \(\varphi^{-1}(m)\) if \(\varphi^{-1}(r)\) is known for all \(r <m\). If \(v_o(m)\) and \(v_e(m)\) denote, respectively, the number of odd and even elements in \(\varphi^{-1}(m)\), this method yields the result that if \(k\ge 1\) and \(s\) is odd then \(v_e(2^ks) = v_o(2^ks) + v_e(2^{k-1}s)\). Assuming that \(2^k +1\) is composite for \(k > 16\) it is shown that \(v_o(2^k) = 1\) if \(0\le k\le 31\) and \(v_o(2^k) = 0\) if \(k\ge 32\). This was first proved by \textit{R. D. Carmichael} [Bull. Am. Math. Soc. 13, 241--243 (1907; JFM 38.0236.01)]. Unfortunately there appears to be no simple way to determine \(v_o(2^ks)\) if \(s >1\).