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

Question

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.

Answer 1

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

Using Highest power of a prime $p$ dividing $N!$,

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

Answer 2

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\}}$.

Answer 3

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

Answer 4

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}$.