# Finding the GCD of $50!$ and $2^{50}$

I've been trying to figure out how $n!$ and $x^n$ are related (where x is an integer) for most of the morning - I know it must be the key to unlocking this problem.

Up to this point I've only used the Extended Euclidean Algorithm to find GCDs, but I know that's not going to work in this case.

The hard part is obviously coming up with the key insight / theorem to apply. If anyone can help me get that insight without telling me outright, that would be awesome. Otherwise, a hint is much appreciated.

Thanks.

• The question can be rephrased as What is the highest power of $2$ that divides $50!$ ? In this form, it is a standard question. – lhf Nov 29 '13 at 17:39
• Not to discourage you, but it's not the "key" - it's actually the problem itself. – Don Larynx Nov 29 '13 at 17:40
• The key to what problem? – dfeuer Nov 29 '13 at 17:40
• P.S. Keys don't have insights...they are complete - but enough. – Don Larynx Nov 29 '13 at 17:41
• The problem: find the gcd(50!, 2^50)- more specifically, I've only ever solved GCDs with EEA. Then this problem comes along, and I can't use the EEA. It requires a deeper understanding, which is what I'm trying to gain by posting here. – astudent Nov 29 '13 at 17:46

Observe that the only prime factor of $2^n($ where $n\ge1)$ is $2$

the highest power of $2$ in $50!$ will be $$\sum_{1\le r<\infty}\left\lfloor\frac{50}{2^r}\right\rfloor=25+12+6+3+1=47$$

The number of factors of a prime $p$ that divides $n!$ is $$\frac{n-\sigma_p(n)}{p-1}$$ where $\sigma_p(n)$ is the sum of the digits in the base-$p$ representation of $n$.

$50=110010_\text{two}$, so $\sigma_2(50)=3$ and the number of factors of $2$ that divides $50!$ is $\frac{50-3}{2-1}=47$. Thus, $\gcd\left(50!,2^{50}\right)=2^{47}$.

$\forall a,b \in \Bbb N, a\land b = \operatorname{gcd}(a,b)$

Let $f(n)=\max\Big\{k\in \Bbb N\,\Big|\, 2^k \mid n\Big\}=\#\Big\{k\in \Bbb N^*\,\Big|\, 2^k \mid n\Big\}$. What properties does this function have?

-

$\forall a,b \in \Bbb N, f(ab)=?$

-

$\forall a,b \in \Bbb N, f(ab)=f(a)+f(b)$

-

$\forall m\in \Bbb N, \forall a_1,\dots,a_m \in \Bbb N, f\left(\prod\limits_{i=1}^na_i\right)=?$

-

$\forall m\in \Bbb N, \forall a_1,\dots,a_m \in \Bbb N, f\left(\prod\limits_{i=1}^na_i\right)=\sum\limits_{i=1}^nf(a_i)$

-

$\forall a,b \in \Bbb N, f(a\land b)=?$

-

$\forall a,b \in \Bbb N, f(a\land b)=\min(f(a), f(b))$

-

$f(50!\land 2^{50})=?$

-

$f(50!\land 2^{50})=\min(f(50!),f(2^{50}))=\min\left(\sum\limits_{i=2}^{50}f(i),50\right)$

-

$\sum\limits_{i=2}^{50}f(i)=\sum\limits_{i=2}^{50}\#\Big\{k\in \Bbb N^*\,\Big|\, 2^k \mid i\Big\}=\sum\limits_{j=1}^{+\infty}\#\Big\{i\in \Bbb N, 2\le i\le 50\,\Big|\, 2^j \mid i\Big\}=\sum\limits_{j=1}^{+\infty}\left\lfloor\cfrac{50}{2^j}\right\rfloor$ Imagine the real axis and place the natural number on it. Now, over each natural number, pile up square boxes, one per $i$ so that $2^i$ divides your number. The left sum is counting the boxes column by column while the right sum is counting them line by line.

You will need to use the fundamental theorem of arithmetic, which says that every natural number has a unique prime factorization. The rest is a matter of finding a sufficiently efficient counting technique.

More specifically, if $x=p_1^{j_1}p_2^{j_2}\dotsm p_n^{j_n}$ and $y=p_1^{k_1}p_2^{k_2}\dotsm p_n^{k_n}$, then $\gcd(x,y)=p_1^{\min\{j_1,k_1\}}\dotsm p_n^{\min\{j_n,k_n\}}$.