Divisibilité et factorielle
dans Arithmétique
Bonjour
Je cherche à montrer $n! \mid (2^n - 1)(2^n - 2)(2^n - 2^2)\dots(2^n - 2^{n-1})$.
J'introduis pour cela l'entier $2^n \choose {2^{n-1} - 1}$ $= \frac{(2^n)!}{(2^n - 2^{n-1} +1)!(2^{n-1} -1)!} = \frac{1}{(2^{n-1} + 1)!} 2^n (2^n - 1)(2^n - 2)(2^n - 3) (2^n - 4)\dots(2^n - 2^{n-1})$
car $2^n - 2^{n-1} = 2^{n-1}$ (ce qui justifie les deux égalités).
On a donc que $(2^{n-1} +1)!$ divise $2^n (2^n - 1)(2^n - 2)(2^n - 3) (2^n - 4)\dots(2^n - 2^{n-1})$ et, puisque $2^{n-1} + 1 \geq n$, que
$n! \mid 2^n (2^n - 1)(2^n - 2)(2^n - 3) (2^n - 4)\dots(2^n - 2^{n-1})$.
Comment conclure à présent ? Je ne pense pas que le produit des $2^n - p$ pour $p < 2^{n-1}$ pas une puissance de $2$ soit premier avec $n$ donc je ne peux pas appliquer Gauss.
Je cherche à montrer $n! \mid (2^n - 1)(2^n - 2)(2^n - 2^2)\dots(2^n - 2^{n-1})$.
J'introduis pour cela l'entier $2^n \choose {2^{n-1} - 1}$ $= \frac{(2^n)!}{(2^n - 2^{n-1} +1)!(2^{n-1} -1)!} = \frac{1}{(2^{n-1} + 1)!} 2^n (2^n - 1)(2^n - 2)(2^n - 3) (2^n - 4)\dots(2^n - 2^{n-1})$
car $2^n - 2^{n-1} = 2^{n-1}$ (ce qui justifie les deux égalités).
On a donc que $(2^{n-1} +1)!$ divise $2^n (2^n - 1)(2^n - 2)(2^n - 3) (2^n - 4)\dots(2^n - 2^{n-1})$ et, puisque $2^{n-1} + 1 \geq n$, que
$n! \mid 2^n (2^n - 1)(2^n - 2)(2^n - 3) (2^n - 4)\dots(2^n - 2^{n-1})$.
Comment conclure à présent ? Je ne pense pas que le produit des $2^n - p$ pour $p < 2^{n-1}$ pas une puissance de $2$ soit premier avec $n$ donc je ne peux pas appliquer Gauss.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tu peux par exemple t'en sortir comme cela: $\qquad u_n: = \displaystyle \prod_{k=1}^{2^{n-1}} (2^n-k).$
Le fait que $n! \mid 2^n u_n$ entraîne que pour tout $p$ premier impair, $\ v_p (n!) \leqslant v_p(u_n).\quad (\forall x \in \N^*,\:v_p(x) $ désigne le plus grand entier $\alpha$ tel que $p^{\alpha} \mid x.)$
D'autre part, $ \ \forall n \in \N^*, \ n \leqslant 2^{n-1}, \quad v_2(n!)\leqslant v_2 \left( (2^{n-1})!\right ) =v_2(u_n).\quad$ Il s'ensuit que : $$ n! \:\text{divise}\: u_n.$$
Le quotient est la suite A053601 de l'OEIS.
Après mon erreur de lecture de l'énoncé, je reprends avec le "bon" $ u_n = \displaystyle \prod _{k=0}^{n-1} (2^n - 2^k) =2^{n(n-1)/2}\prod_{k=1}^n (2^k-1).$
Le plus simple est bien entendu de dire que $\dfrac{u_n}{n!}$ est le nombre de $n$ -parties de $\mathbb F_2^n$ qui engendrent $\mathbb F_2^n,\:$ et donc : $\: n! \:\text{divise}\: u_n.$
On peut aussi s'amuser à dégotter un "argument arithmétique".
Il est connu (uniquement de ceux qui le savent) que: $ v_2 (n!)<n,\:\:(\star)\quad$ et d'autre part: $\: v_2 (u_n) = \dfrac {n(n-1)} 2$, donc: $\quad\boxed{ v_2(n!)< v_2(u_n).}$
Soit $p$ un nombre premier impair et $A_p = \{ a \in [\![1;n]\!] \mid a \equiv 0 \mod p \}.\quad \:\:$ Alors $v_p(n!) = \displaystyle \sum _{a\in A_p} v_p(a)$
Soit $ f: A_p \longrightarrow [\![1;n]\!],\:\: a \longmapsto \dfrac{(p-1)a}p. \: f$ est injective. $\quad \varphi$ désigne la "fonction d'Euler": $\varphi (n) = \text{Card}\{x\in \N\mid 1\leqslant x \leqslant n,\:\: x\wedge n = 1 \}.$
Soit $a =p^sq \in A_p,\:\:\:\: p\wedge q= 1.\quad$ Alors $\:\:2 ^{f(a)} -1=(2^q)^{\varphi(p^s)} -1 \equiv 0 \mod p^s. \quad$ (Théorème d'Euler).
Ainsi: $ \quad v_p (2^{f(a)}-1) \geqslant v_p(a),\qquad v_p(u_n) \geqslant \displaystyle \sum _ {a \in A_p} v_p( 2^{f(a)}-1) \geqslant \sum_{a\in A_p}v_p(a) = v_p(n!).\qquad \boxed {v_p(n!)\leqslant v_p(u_n).}$
$$ \boxed{ n! \:\:\text{divise}\:\: u_n.}$$
Preuve de $(\star)\qquad \forall n \in \N^*, \:\:\forall p \:\text{premier}:$
$ v_p(n!) = \displaystyle \sum_{k=1}^{+\infty} k \:\left( \text{Card}\left(p^k\Z \cap [\![1;n]\!]\right) -\text{Card}\left(p^{k+1}\Z \cap [\![1;n]\!]\right)\right) = \sum_{k =1}^{+\infty} k \left( \Big\lfloor \frac n{p^k}\Big\rfloor- \Big\lfloor \frac n{p^{k+1}} \Big\rfloor \right) =\sum _{k=1} ^{+\infty} \Big\lfloor \frac n{p^k}\Big\rfloor < \sum _{k=1}^{+\infty} \frac n {p^k} =\frac n{p-1}.$
J'ai obtenu qu'il divise $2^n \displaystyle \prod_{k =1}^{2^{n}-1}(2^n - k)$
Si tu sais que $\mathfrak S_n$ s'injecte dans $GL_n(\mathbb F_2)$ groupe des matrices inversibles de taille $n$ sur le corps $\mathbb F_2$, en envoyant la permutation $\sigma$ sur la matrice de permutation correspondante (la colonne $i$ a un $1$ en position $\sigma(i)$ et $0$ ailleurs) ;
si tu sais que l'ordre de $GL_n(\mathbb F_2)$ est le nombre de bases de $\mathbb F_2^{\,n}$, soit
$2^n-1$ pour le premier vecteur de base (non nul),
$2^n-2$ pour le deuxième (tous sauf la droite déterminée par le premier vecteur de la base),
$2^n-2^2$ pour le troisième (tous sauf le plan déterminé par les deux premiers vecteurs)
etc. ;
alors il ne te reste plus qu'à invoquer Lagrange.
Alain
On peut démontrer un résultat plus fort pour $n\geq2$ : $(n+1)!$ divise $u_n=\displaystyle \prod _{k=0}^{n-1} (2^n - 2^k) =2^{n(n-1)/2}\prod_{k=1}^n (2^k-1).$
Pour $p=2$ : $3!=u_2$ et si $n\geq3$ on a $v_2((n+1)!)\leq n\leq\dfrac{n(n-1)}2=v_2(u_n)$.
Soit $p$ premier impair. En utilisant $\varphi(p^k)=p^{k-1}(p-1)$ et le théorème d'Euler on obtient : $v_p\left(\displaystyle\prod_{k=1}^n (2^k-1)\right)\geq \displaystyle\sum_{k\geq1}\left\lfloor\dfrac n{p^{k-1}(p-1)}\right\rfloor$.
Comme pour $p\leq n+1$ on a $\dfrac{n+1}{p^k}\leq\dfrac n{p^{k-1}(p-1)}$ on a bien $v_p((n+1)!)\leq v_p(u_n)$.