Finding GCD of powers and factorial numbers

Question

I need some help with trying to find the GCD of $23!$ and $2^{31}$. I tried writing out the prime factor of 23! but I am still left with lots of exponents. However, the prime factorial of $23!$ includes $2^{19}$ and I am wondering how I could use this. I understand how to solve this using the Euclidean Algorithm, but trying to divide these large numbers is confusing me a lot, and I'm wondering if there are other methods/tricks? Any help or insight would be appreciated!

Answer 1

You want to find greatest common divisor of two numbers. Thus, you are looking for a number which divides both of your numbers. Since, one of your numbers is $2^{31}$, it is only divisible by numbers of the form $2^{m}$ for $m=1,2,..,31$. Also, you want to find the greatest number that divides $2^{31}$ and $23!$. Hence, your question reduces to: Find the largest natural number $n$ which is less than or equal to $31$ such that $2^{n}$ divides $23!$. Once you find it, $2^{n}$ is the answer of your question.

Answer 2

Hint:

The g.c.d. you seek is necessarily a power of $2$. Now you have Legendre's formula to obtain the exponent $v_p(n!)$ of any prime $p$ in $n!\,$: $$v_p(n!)=\biggl\lfloor\frac n p\biggr\rfloor+\biggl\lfloor\frac n {p^2}\biggr\rfloor++\biggl\lfloor\frac n {p^3}\biggr\rfloor+\dotsm$$ (this is actually a finite sum).