Complexity of Least Common Multiple

Question

I would like to know the complexity of computing the least common multiple of $n$ natural numbers. Does it depend on Euler's totient function?

Answer 1

We assume that our numbers $(a_i)_i$ have at most $\alpha$ bits ($l(a_i)\leq \alpha$). We calculate the following values: $\gcd(a_1,a_2),{\rm lcm}(a_1,a_2),\gcd(\mathrm{lcm}(a_1,a_2),a_3),{\rm lcm}(a_1,a_2,a_3),\cdots $. When $a>b$, the complexity (number of elementary operations with respect to bits) $C_G(a,b)$ of the calculation of $\gcd(a,b)$ satisfies $C_G(a,b)\leq l(a)l(b)+\lambda.l(b)^2$; then $C_L(a,b)$, the complexity of $\mathrm{lcm}(a,b)$, satisfies $C_L(a,b)\leq 2.l(a)l(b)+\lambda.l(b)^2$. Note that $l({\rm lcm}(a_1,\cdots,a_k))\leq k\alpha$. Finally , the total complexity $C$ satisfies $C\leq (2\alpha ^2+\lambda\alpha ^2)+(4\alpha ^2+\lambda\alpha ^2)+(6\alpha ^2+\lambda\alpha ^2)+\cdots\leq (n²+n\lambda)\alpha ^2$.

Answer to Hans. Finally I don't think that U: "a simple algorithm" (your reference in wiki) is powerful. For instance, consider $lcm(99,100,101,103)=99.100.101.103$. U uses $\approx 10^6$ additions of the form $p+a$ where $a\in\{99,100,101,103\}$, that is an exponential complexity.