Préambule

Le sujet

Les sujets proposés cette année 2017-2108 sont disponibles ici.
Pour ma part, j’ai choisi celui qui me correspondait le plus, puisque relevant de la théorie des nombres : « PGCD des coefficients binomiaux ».

Approche mathématique

Question 1

Soit $n$ un nombre entier non nul.
On suppose que $n$ est premier. Déterminer le $PGCD$ des coefficients binomiaux
$$
{n\choose1}, {n\choose2},\ldots, {n\choose{n-1}}
$$

---

Rappel :
En mathématiques, les coefficients binomiaux, définis pour tout entier naturel $n$ et tout entier naturel $k$ inférieur ou égal à $n$, donnent le nombre de parties de $k$ éléments dans un ensemble de $n$ éléments. Wikipedia 

La formule permettant de calculer un coefficient binomial peut s’écrire sous la forme :$$\frac{n!}{k!(n-k)!}$$
Sachant que les coefficients binomiaux sont entiers, on en déduit que : $k!(n-k)!\mid{n!}$

Puisque $n$ est premier,
$$
\forall \, k \in [\![ 1;n-1 ]\!] \quad \exists \, q \in \mathbb{N^*}, \quad \frac{n!}{k!(n-k)!} =n\times q
$$

Les coefficients binomiaux sont donc tous divisibles par $n$. De plus, les plus petits sont
$$
{n\choose1} \text{ et } {n\choose{n-1}}
$$
De manière évidente, leur valeur est $n$.
Puisque la plus grande valeur commune à tous les coefficients est également $n$, c’est le $PGCD$ recherché. $\qquad \blacksquare$

Question 2

Montrer que pour tout entier $n$, $n^p-n$ est divisible par $p$ premier.

---

Application du petit théorème de Fermat et de la démonstration par récurrence. 

Sachant que $n^p-n=n(n^{p-1}-1)$ :

• soit, $n=k\times p$ et donc $n^p-n=kp(n^{p-1}-1)$ $\Rightarrow$ $p\mid n^p-n $
• soit $p\nmid n$, et d’après le petit théorème de Fermat :
  $$
  p\mid n^{p-1}-1, \quad \text{ avec } p \text{ premier }
  $$

On en déduit que dans tous les cas $p \mid n^p-n$. $\qquad \blacksquare$

Nous pouvons également démontrer ce théorème grâce au principe de récurrence :

Pour tout entier $n \ge 1$, on définit $\mathcal{P}_n$ la propriété : si $p$ est premier, $p \mid n^p-n$.

• Initialisation

Soit $n=1$, on a $1^p-1=0$. $\mathcal{P}_1$  est donc vraie.

• Hérédité

Supposons $\mathcal{P}_n$ vraie et montrons que $\mathcal{P}_{n+1}$ est vraie.

Posons $P(n) = n^p-n$

\begin{eqnarray*}
P(n+1) &=& (n+1)^p-(n+1) \\
&=& n^p+\color{red}{{p\choose 1} n^{p-1}+{p\choose 2} n^{p-2}+\ldots }+1-(n+1)
\end{eqnarray*}
D’après Question 1, nous savons que les coefficient binomiaux sont divisibles par $p$ premier, donc il faut et il suffit que $n^p+1-(n+1)$ soit divisible par $p$. Or, d’après l’hypothèse de récurrence, $p \mid n^p-n$, on en conclut que $p\mid P(n+1)$ et donc $\mathcal{P}_{n+1}$ vraie.

Finalement, $\mathcal{P}_n$ vraie pour tout entier $n$.$\qquad \blacksquare$

Question 3

Quel est le $PGCD$ des coefficients binomiaux si $n$ est une puissance $m$ d’un nombre premier $p$ ?

---

Utilisation du lemme de Gauss. 

Nous savons que le plus petit coefficient est égal à $n$ soit $p^m$, le $PGCD$ est donc de la forme $p^q$ avec $q\le m$.
On sait que :

$$
{n\choose k} = \frac{n \times (n-1) \times \ldots \times (n-(k-1))\times \color{red}{(n-k) \times (n-(k+1))\times \ldots \times 2 \times 1}}{k!\color{red}{ 1 \times 2 \times \ldots \times (n-k)}}
$$

On a donc pour $k = p^{m-1}$ :

$$
{p^m\choose p^{m-1}} = p \times \prod_{i=1}^{p^{m-1}-1} \left( \frac{p^m-i}{p^{m-1}-i} \right)
$$

$p$ étant indivisible, supposons qu’il existe un certain $i$, tel que:

$$
p^{~j} \mid \left( p^m-i \right)
$$
avec $1\le j \le m-1$.

Puisque $p^{~j} \mid p^{m}$, alors $p^{~j} \mid i$.

Ceci implique qu’il divise de la même manière le numérateur et le dénominateur $\left( p^{m-1}-i \right)$, et donc :

$$
p \text{ ne divise pas } \prod_{i=1}^{p^{m-1}-1} \left( \frac{p^m-i}{p^{m-1}-i} \right)
$$

Le $PGCD$ cherché est donc $p$. $\qquad \blacksquare$

Question 4

Déterminer une formule donnant le $PGCD$ de $${2n\choose2}, {2n\choose4},\ldots, {2n\choose{2n-2}}$$

---

Conjecture, démonstration non finalisée. 

Nous avons à partir d’exemples, émis une hypothèse, que nous avons par la suite testée à l’aide d’un programme.

Soit $B=\{b_k\}$ l’ensemble des bases de décomposition de l’entier $2n$, avec $b_k \geq 3$ et premier, et tel que : $2n = b_k^i + b_k^{j}, \quad i,j \text{ entiers}$

• Si $B$ est vide, $PGCD = 1$
• Sinon :
  • Si $2n = 2^m, \quad m \text{ entier}, \quad PGCD = \textbf{2}\times \prod_k b_k$
  • Sinon $PGCD=\prod_k {b_k}$

Voici trois exemples :

• $\textbf{2n=6}$

$6 = 3^1 + 3^1 = 5^1 + 5^0 \quad PGCD{6 \choose 2k} = 3 \times 5\quad k\in[\![ 1;2 ]\!]$

•  $\textbf{2n=128}$

$128 = 2^7 = 127^0 + 127^1$ \quad $PGCD{128 \choose 2k} = 2 \times 127\quad k\in [\![ 1;62]\!]$

• $\textbf{2n=40}$

$PGCD{40 \choose 2k} = 1 \quad k\in [\![ 1;19]\!]$

Nous n’avons pu réaliser qu’un sens de la démonstration en montrant que tous les $b_k$ apparaissent dans le $PGCD$.

Soit $n_1 = p^\alpha$, $n_2 = p^\beta$ tels que $n_1 + n_2 = 2n$ et $p$ premier différent de $2$. On peut alors écrire :

\begin{eqnarray}
(x + y)^{2n} &=& \sum_{i=0}^{2n} {2n \choose i} x^{i} y^{2n-i} = (x + y)^{n_1}(x + y)^{n_2} \\
&=&\sum_{j=0}^{n_1} {n_1\choose j}x^jy^{n_1-j}\times \sum_{k=0}^{n_2} {n_2\choose k}x^ky^{n_2-k} \\
&=&\sum_{j=0}^{n_1} \sum_{k=0}^{n_2} {n_1\choose j} {n_2\choose k}x^{j+k}y^{2n -(j+k)}
\end{eqnarray}
On identifie les coefficients binomiaux tels que $j+k=2i$ :

$${2n\choose 2i} = \sum_{j+k=2i} {n_1\choose j} {n_2\choose k}$$

Soit :
$${2n\choose 2i} = \sum_{q=0}^{2i} {n_1\choose q} {n_2\choose 2i – q} $$

C’est l’identité de Vandermonde, que l’on peut démontrer également en mathématiques combinatoires.
Dans cette somme de produits, on distingue quatre cas pour lesquels un terme peut valoir $1$ et ne serait donc pas divisible par $p$ :

• $q=0$ et $2i=0$, ce qui est impossible car $i\in [\![ 1 ; n-1 ]\!]$
• $q=0$ et $2i=n_2$, $n_2$ étant impair c’est également impossible
• $q=n_1$ et $2i=n_1$, mais $n_1$ doit aussi être impair
• $q=n_1$ et $2i=n_2+n_1$ mais $i \in [\![ 1 ; n-1 ]\!]$

Comme on l’a vu (Question 3) sachant que $n_1$ et $n_2$ sont des puissances de nombres premiers, $p$ divise le $PGCD$.

Maintenant que se passe t-il si $p=2$ ?

$2n = 2^\alpha + 2^\beta$

$${2n\choose 2i} = \sum_{q=0}^{2i} {2^\alpha\choose q} {2^\beta\choose 2i – q} $$
Cherchons les cas pour lesquels un des produits est $1$ :

	$2i – q = 0$	$2i – q = 2^\beta $
$q = 0$	$i = 0$ imp	$i = 2^{\beta – 1}$
$q = 2^\alpha$	$i = 2^{\alpha – 1}$	$i = n$ imp

• Si $\alpha \neq \beta$, il existe deux valeurs distinctes de $i$ ($2i=2^\alpha$ et $2i=2^\beta$)telles que $2\nmid {2n\choose 2i}$.
  Si $2$ ne divise pas tous les coefficients alors il ne divise pas non plus le $PGCD$.
• Si $\alpha=\beta$, on additionne deux produits impairs ${2^\alpha \choose 2^\alpha}{2^\alpha \choose 0}$ et ${2^\alpha \choose 0}{2^\alpha \choose 2^\alpha}$, le résultat sera donc pair.
  Or, $2n=2\times 2^\alpha$ donc $2n$ est une puissance de $2$.
  Finalement, $2\mid PGCD$ si et seulement si $2n$ est une puissance de $2$.

Pour conclure, si $2n = b_k^i + b_k^j$ avec $b_k\ge 3$ et premier, alors $\prod b_k \mid PGCD$.
De plus, si $2n$ est une puissance de $2$ alors $2\mid PGCD$.

Nous n’avons pas réussi à démontrer qu’aucun autre facteur ne divise le $PGCD$.

Approche numérique

Voici des extraits d’algorithmes, tirés d’un programme python, servant à tester notre conjecture
sur une grande échelle de valeurs.

Nous nous sommes limitées à $2n = 1000 (PGCD = 1)$, et jusqu’à cette valeur la conjecture est vérifiée.

En modifiant légèrement le programme nous avons également remarqué des comportements similaires avec ${3n\choose 3i}$, à la différence près que les particularités observées pour les puissances de $2$ deviennent celles des puissances de $3$.