# evaluate $\phi(50!)$

I want to evaluate $\phi(50!)$, where $\phi$ is the Euler totient function, so i take the factorization in primes of $50!$ $$2^{47}\times 3^{22}\times 5^{12}\times 7^8\times 11^4\times 13^3\times 17^2\times 19^2\times 23^2\times 29\times 31\times 37\times 41\times 43\times 47$$ then i use multiplicativity of $\phi$ and the properties $\phi(p)=p-1$ and $\phi(p^k)=p^{k-1}(p-1)$ for every prime $p$ and i get $$\phi(50!)=4218559200885839042679312107816703841788854953574400000000000000$$

I'm asking for some smarter way to compute values of $\phi$ for great numbers, possibly not involving prime factorization

• I would say that factorizing is a pretty strong way to do this. If you look only for a fast calculator, Pari/GP does it fast. – Beni Bogosel Mar 18 '13 at 22:02
• No one knows a better way to get $\phi$ than by factorization. Indeed, in many contexts the two problems are equivalent, in that if you can do either one then you can do the other just as fast. – Gerry Myerson Mar 18 '13 at 23:28
• Saying you need factorization of $n!$ suggests something worse than it really is; there are only prime factors${}\leq n$ and there is a pretty simple formula for the multiplicity of such prime factors. But as the answer by DonAntonio shows, you don't even need that formula if you are willing to do a few divisions in addition to multiplications. – Marc van Leeuwen Mar 19 '13 at 11:03

$$\phi(50!)=50!\prod_{p\le 50\,,\,\,p\text{ a prime}}\left(1-\frac{1}{p}\right)$$

The above is based on the following lemma:

Lemma: If

$$\Bbb N\ni n=\prod_{i=1}^kp_i^{a_i}\;\;,\;\;0<a_i\in\Bbb N\;,\;\;p_i\,\,\text{primes}$$

is the prime decomposition of $\,n\,$ , then

$$\phi(n)=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$$

• in the last $\displaystyle\prod$, do you mean $i$ from 1 to $k$? – bateman Mar 19 '13 at 7:59
• Indeed, so, thanks. – DonAntonio Mar 19 '13 at 10:51