Prove that $\prod\limits_{k=0}^{n-1}{({{2}^{n}}-{{2}^{k}})}$ is divisible by $n!$ for all positive integers $n$.
Problem
Source: Turkish NMO 1996, 5. Problem
Tags: group theory, abstract algebra, floor function, modular arithmetic, number theory proposed, number theory
ZetaX
01.08.2011 02:12
That product is the size of $\mathrm{Gl}_n(\mathbb Z/2)$, which contains $S_n$ as a subgroup via permutation matrices. Lagrange's theorem then does the rest.
efoski1687
07.08.2011 14:37
to Zetax: Do you know an elementar solution, if you have such one, could you please post it?
SCP
07.08.2011 15:20
efoski1687 wrote: Prove that $\prod\limits_{k=0}^{n-1}{({{2}^{n}}-{{2}^{k}})}$ is divisible by $n!$ for all positive integers $n$. easier: Look to each prime factor, for $p=2$ we have $\frac{n(n-1)}{2}$ factors $2$ which is bigger than $n$ for $n>3$ and the other ones are easy to check. For $p$ odd (other primes): $p|2^{p-1}-1$ by Fermat and so if $p-1|n-k$ we get at least one prime factor $p$ and similar if $(p-1)p^r|n-k$ and we have there $n$ ways to choose $k.$ Doing this it becomes $\sum_{i=0}^{n} [\frac{n}{(p-1)p^i}]>\sum_{i=0}^{n} [\frac{n}{p^{i+1}}]$ which is trivial.
ZetaX
08.08.2011 03:43
efoski1687 wrote: to Zetax: Do you know an elementar solution, if you have such one, could you please post it? See SCP. But given a person having no knowledge in neither kind of mathematics relevant to this, I even think that the Lagrange-based solution takes less effort to fully prove Especially, I wouldn't say it's not elementary. Noncanon for school level problems, maybe
SCP
08.08.2011 16:34
ZetaX wrote: But given a person having no knowledge in neither kind of mathematics relevant to this, I even think that the Lagrange-based solution takes less effort to fully prove For ex. me (have some knowledge in NT), but don't know sth of the field/group you construct, it isn't possible to fulfil I think. While I suppose everybody can understand the more easy stuff I use. So the way of simple is different; short solution using more advanced methods vs longer solution using simple ideas. Correct? Otherwise, it is maybe easy to explain the way you used and wrote in two lines, so we will see it is quite easy (but now it seems too advanced), for ex. search to $ \mathrm{Gl}_{n}(\mathbb{Z}/2) $ for extra information by yourself is more difficult than finding the formula for number of a prime in $n!$.
exmath89
15.04.2013 00:42
Note that by taking $k$ factors of $2$ out of $2^n-2^k$ for $0\le k\le n-1$, we can rewrite the product as
\[ A=\prod_{k=0}^{n-1}({{2}^{n}}-{{2}^{k}}) =2^{\frac{n(n-1)}{2}}\prod_{k=1}^n(2^k-1).\]
Let $p$ be an arbitrary prime, and let $v_p(n)$ denote the number of factors of $p$ in $n$. It is well known that $v_p(n!)=\sum^{\infty}_{k=1}\left\lfloor\frac{n}{p^k}\right\rfloor=\frac{n-s_p(n)}{p-1}$, where $s_p(n)$ is the sum of the digits of $n$ in base $p$. For $p=2$, note that
\[ v_2(n!)=n-s_2(n)\le n-1\le\frac{n(n-1)}{2}=v_2(A).\]
Now let $p$ be an odd prime. Since $\phi(p^i)=p^{i-1}(p-1)$ for $i\ge 1$, by Euler's Totient Theorem, $2^{k}\equiv1\pmod{p^i}$ when $k$ is a multiple of $p^{i-1}(p-1)$. It follows that
\[ v_p(n!)=\sum^{\infty}_{k=1}\left\lfloor\frac{n}{p^k}\right\rfloor\le\sum^{\infty}_{k=1}\left\lfloor\frac{n}{p^{k-1}(p-1)}\right\rfloor=v_p(A).\]
Hence, $v_p(n!)\le v_p(A)$ for all primes $p$, so $n!|A$. //
dibyo_99
15.04.2013 05:26
The given product is actually $2^{\frac{n(n-1)}{2}}\prod_{k=1}^n(2^k-1)$. We will denote this number by $A$. We know that $v_2(n!) = n-s_2(n) \le \frac{n(n-1)}{2}$. So, $v_2(n!) \leq v_2(A)$. Now consider any odd prime $p$. Using Euler's Theorem $2^{\varphi(p^i)} =2^{p^{i-1}(p-1)} \cong 1(mod$ $p^i)$. And $v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor \le \sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^{k-1}(p-1)}\right\rfloor=v_p(A)$. So, for all primes $p$, $v_p(n!) \le v_p(A)$. Hence $n!|A$.
darij grinberg
21.04.2013 08:38
exmath89 wrote:
Note that by taking $k$ factors of $2$ out of $2^n-2^k$ for $0\le k\le n-1$, we can rewrite the product as
\[ A=\prod_{k=0}^{n-1}({{2}^{n}}-{{2}^{k}}) =2^{\frac{n(n-1)}{2}}\prod_{k=1}^n(2^k-1).\]
Let $p$ be an arbitrary prime, and let $v_p(n)$ denote the number of factors of $p$ in $n$. It is well known that $v_p(n!)=\sum^{\infty}_{k=1}\left\lfloor\frac{n}{p^k}\right\rfloor=\frac{n-s_p(n)}{p-1}$, where $s_p(n)$ is the sum of the digits of $n$ in base $p$. For $p=2$, note that
\[ v_2(n!)=n-s_2(n)\le n-1\le\frac{n(n-1)}{2}=v_2(A).\]
Now let $p$ be an odd prime. Since $\phi(p^i)=p^{i-1}(p-1)$ for $i\ge 1$, by Euler's Totient Theorem, $2^{k}\equiv1\pmod{p^i}$ when $k$ is a multiple of $p^{i-1}(p-1)$. It follows that
\[ v_p(n!)=\sum^{\infty}_{k=1}\left\lfloor\frac{n}{p^k}\right\rfloor\le\sum^{\infty}_{k=1}\left\lfloor\frac{n}{p^{k-1}(p-1)}\right\rfloor=v_p(A).\]
Hence, $v_p(n!)\le v_p(A)$ for all primes $p$, so $n!|A$. //
dibyo_99 wrote: The given product is actually $2^{\frac{n(n-1)}{2}}\prod_{k=1}^n(2^k-1)$. We will denote this number by $A$. We know that $v_2(n!) = n-s_2(n) \le \frac{n(n-1)}{2}$. So, $v_2(n!) \leq v_2(A)$. Now consider any odd prime $p$. Using Euler's Theorem $2^{\varphi(p^i)} =2^{p^{i-1}(p-1)} \cong 1(mod$ $p^i)$. And $v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor\frac{n}{p^k}\right\rfloor \le \sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^{k-1}(p-1)}\right\rfloor=v_p(A)$. So, for all primes $p$, $v_p(n!) \le v_p(A)$. Hence $n!|A$. Gotta love the identical notations and almost identical wording.
SidVicious
06.07.2016 15:09
stronger result: Given $q,n,r \in \mathbb N$ and $r \le n$. Prove that: $$r! | \prod_{i=0}^{r-1}(q^n-q^i)$$as for the proof, divide problem in 2 cases: 1. $p|q$ 2. $p$ doesnt divide $q$ ($p$ is prime divisor of $r$) and in both cases prove $v_p(r!) \le v_p ( \prod_{i=0}^{r-1}(q^n-q^i))$
grupyorum
17.02.2018 04:45
Actually, in two of the above solutions, there is a minor bug (or at least I think that there is). Basically, they attempt to count the powers of $p$, let's say, $p^k \leq n <p^{k+1}$ for a prime $p\leq n$, hence we need to take care of terms, that are divisible by $p^{\beta}$, where $\beta\in\{1,2,\dots,k\}$. Let, $d_n$ be the smallest integer so that, $2^{d_n}\equiv 1 \pmod{p^n}$. Then, $d_{n+1}=pd_n$ (and using this, left hand side is simply counting the multiples of $p^n$, that ($multiple/p^n$) are not divisible by $p$, while, the right hand side are counting the multiples of $d_n$, where, $multiple/d_n$ is not divisible by $p$; and both of these multiple searchs are carried on $\{1,2,\dots,n\}$. Since, $d_n \leq \phi(p^n)=p^n-p^{n-1}$, we have the result. To see the claim above, simply note that if $2^{d_n}\equiv 1 \pmod{p^n}$, and $d_{n+1}$ defined similarly, then, $d_n \mid d_{n+1}$. Letting, $d_{n+1}=kd_n$, and expanding, $$ 2^{d_{n+1}}-1 = \underbrace{(2^{d_n}-1)}_{p^n\mid\mid}\underbrace{((2^{d_n})^{k-1}+(2^{d_n})^{k-2}+\cdots+1)}_{\equiv k \pmod{p}}, $$hence, if $k<p$, it won't work (also ask yourself, why $p^n \mid \mid 2^{d_n}-1$).