OK so I have this math problem that I am not sure on how to solve. Bellow is the question.
- Find the greatest common divisor of $100!$ and $(3072\times 7^{10}\times 23^5 \times 59^2)$.
Give the answer as a product of powers of primes.
OK so I know that I have to collect the common prime factors with the smallest element. So how to I do that especially with $100!$ being a very large number.
Any assistants would be appreciated.
On
We can use Legendre's Formula here.
The number of factors of $2$ in $100!$ is $\frac{100-3}{2-1}=97$.
The number of factors of $3$ in $100!$ is $\frac{100-4}{3-1}=48$.
The number of factors of $7$ in $100!$ is $\frac{100-4}{7-1}=16$.
The number of factors of $23$ in $100!$ is $\frac{100-12}{23-1}=4$.
The number of factors of $59$ in $100!$ is $\frac{100-42}{59-1}=1$.
Thus, $2^{97}\cdot3^{48}\cdot7^{16}\cdot23^4\cdot59^1$ divides $100!$ Now, using the minimum of the exponents gives $$ \begin{align} \gcd(100!,\,\overbrace{2^{10}\cdot3}^{3072}\cdot7^{10}\cdot23^5\cdot59^2) &=2^{10}\cdot3\cdot7^{10}\cdot23^4\cdot59\\ &=14,\!327,\!320,\!206,\!855,\!570,\!432 \end{align} $$
Hint: Look at the primes in $3072 \cdot 7^{10} \cdot 23^5\cdot 59^2$ and their exponents in the factorization of $100!$. Note that $3072 = 3 \cdot2^{10}$.