Disibility by $n!$
-
- Posts:107
- Joined:Sun Dec 12, 2010 10:46 am
Prove that for all positive integers $n$, $n!$ divides $$\prod (2^n-2^k) $$ for $1\le k \le n-1$.
Re: Disibility by $n!$
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.
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.