Disibility by $n!$

For discussing Olympiad Level Number Theory problems
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
Disibility by $n!$

Unread post by mutasimmim » Fri Mar 27, 2015 7:51 am

Prove that for all positive integers $n$, $n!$ divides $$\prod (2^n-2^k) $$ for $1\le k \le n-1$.

rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm

Re: Disibility by $n!$

Unread post by rah4927 » Tue Mar 31, 2015 1:06 pm

Just some ideas:

My idea is that we need to consider every prime factor of $n!$ and show that the exponent of $p$ in $n!$ is less than or equal to its exponent in the product. First of all, the product can be written in a more convenient form:

$$A=2^{\frac{n(n-1)}{2}}(2^1-1)\cdots(2^{n-1}-1)$$

This form seems to be a natural candidate for induction. However, I am not sure how to use the inductive hypothesis to show that \(n+1\) must necessarily divide $A/n!$.

Legendre tells us how to compute the exponent $e_p$ of $p$ in $n!$. We also know that the exponent of $p,p\neq 2$ in $A$ is $\lfloor \frac{n}{s} \rfloor$, where $s$ is the order of $2$ modulo $p$. Now we have to show that for each prime,$$e_p\ge \lfloor \frac{n}{s} \rfloor$$. Not sure how to proceed from here though. But I think that primes which are very small or are very big might give us good bounds on the exponents.

I haven't experimented much with different values of $n$. Doing so might help. I would be on the lookout for ways to proceed using induction if I did experimentation.

Post Reply