evaluate $\phi(50!)$

181 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

$$\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)$$