Euler's totient function and its inverse (Q1147740)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Euler's totient function and its inverse
scientific article

    Statements

    Euler's totient function and its inverse (English)
    0 references
    0 references
    1981
    0 references
    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\).
    0 references
    inverse
    0 references
    Euler's totient function
    0 references
    constructive method
    0 references

    Identifiers