Some remarks on computing the square parts of integers (Q1112857)

The complexities of the computation of values of several number theoretic functions are compared. For a natural number \(n\in {\mathbb{N}}\) with prime factorization \(\prod p_ i^{a_ i}\) these functions are defined as follows: \(\phi (n)=\prod p_ i^{a_ i-1}(p_ i-1)\) Euler's function; \(\lambda (n)=lcm\{p_ i^{a_ i-1}(p_ i-1)\}\) Carmichael's function; \(\lambda '(n)=lcm\{p_ i-1\}\); \(\theta (n)=\prod p_ i^{a_ i-1}\), square part of n. It is shown that the computation of \(\theta\) is in polynomial time Turing reducible to the computation of \(\phi\) or \(\lambda\). In addition it is shown that the computation of \(\lambda\) ' is in polynomial time reducible to that of \(\lambda\) and the computation of \(\lambda\) is reducible in polynomial time to the computation of both \(\theta\) and \(\lambda\) '. It is conjectured that it is not possible that the computation of \(\theta\) can be reduced to that of \(\lambda\) '.