Le but de cet article est de démontrer qu’un nombre entier $n\geq 2$ est premier, si et seulement si, pour tout entier $k$ compris entre $1$ et $n-1$, le coefficient binomial $\binom{n}{k}$ est divisible par $n.$

Visualisez le triangle de Pascal

Les premières lignes du tableau de Pascal sont les suivantes, à chaque fois est donnée la valeur du coefficient binomial $\binom{n}{k}.$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=0&1 & \\
\hline
n=1&1 & 1\\
\hline
n=2&1 & 2 & 1\\
\hline
n=3&1 & 3 & 3 & 1\\
\hline
n=4&1 & 4 & 6 & 4 & 1\\
\hline
n=5&1 & 5 & 10 & 10 & 5& 1\\
\hline
n=6&1 & 6 & 15 & 20 & 15& 6 & 1\\
\hline
n=7&1 & 7 & 21 & 35 & 35& 21 & 7 & 1\\
\hline
n=8&1 & 8 & 28 & 56 & 70& 56 & 28 & 8&1\\
\hline
\end{array}

En prenant un numéro de ligne qui est un nombre premier, par exemple lorsque $n=7$, vous constatez que les coefficients binomiaux $7$, $21$, $35$, $35$, $21$ et $7$ sont tous des multiples de $7.$ Autrement dit :

\forall k\in\llbracket 1, 6\rrbracket, \quad 7 \left| \binom{7}{k}\right..

Par contre, en prenant $n=6$ qui n’est pas un nombre premier, vous constatez, par exemple que $20$ n’est pas un multiple de $6$, ce qui s’écrit ainsi :

6 \not\left| \binom{6}{3}\right..

Autrement dit :

\exists k\in\llbracket 1, 5\rrbracket, \quad 6 \not\left| \binom{6}{k}\right..

Le premier sens comme conséquence du lemme d’Euclide

Soit $n$ un nombre entier supérieur ou égal à $2.$ Vous supposez que $n$ est un nombre premier.

Soit $k$ un nombre entier compris entre $1$ et $n-1.$ Le coefficient binomial $\binom{n}{k}$ se calcule avec une expression comportant des factorielles :

\binom{n}{k} = \frac{n !}{k ! (n-k) !}.

Vous déduisez de ce qui précède que :

n ! = k ! (n-k) ! \binom{n}{k}.

Comme $n! = n\times (n-1)!$ il s’ensuit que $n$ divise le produit $k! (n-k)! \binom{n}{k}.$

Supposez que $n$ ne divise pas le coefficient binomial $\binom{n}{k}.$ Comme $n$ est un nombre premier qui divise le produit des deux nombres $k! (n-k)!$ et $\binom{n}{k}$ le lemme d’Euclide (vous en trouverez une démonstration dans le contenu rédigé [yanniswp_article_link nb= »126″ desc= »dans l’article 126″]) permet d’affirmer que $n$ divise $k! (n-k)!.$ Toujours d’après le même lemme d’Euclide, $n$ divise un des facteurs noté $i$ du produit $k! (n-k)!.$ Comme $k$ est compris entre $1$ et $n-1$, tous les facteurs du produit $k! (n-k)!$ sont des nombres entiers compris entre $1$ et $n-1.$ Il s’ensuit que $i$ lui-même est un entier compris entre $1$ et $n-1.$

Or, $n$ divise $i$ avec $i$ non nul impose d’avoir $n\leq i.$ Or il a été vu que $i \leq n-1$ ce qui aboutit à une contradiction.

Par l’absurde, il a été prouvé que $n$ divise le coefficient binomial $\binom{n}{k}.$

Ainsi, pour tout entier $n$ supérieur ou égal à $2$, l’implication ci-dessous est démontrée.

\boxed{n \text{ est premier }\implies \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Le sens réciproque comme conséquence de la relation de Pascal et de l’arithmétique modulaire

Visualisez la situation lorsque $n=8$

Supposez que, pour $n=8$, vous ayez :

\forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..

Vous raisonnez modulo $8$ et obtenez :

\forall k\in\llbracket 1, 7\rrbracket, \quad \binom{8}{k} \equiv 0 \mod 8.

En écrivant le triangle de Pascal modulo $8$ pour les lignes $n=7$ et $n=8$ il vient :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=7&1 &  &  &  & &  &  & \\
\hline
n=8&1 & 0 & 0 & 0 & 0& 0 & 0 & 0&1\\
\hline
\end{array}

Pour déterminer le résidu du coefficient binomial $\binom{7}{1}$ modulo $8$, vous utilisez la relation de Pascal :

\binom{7}{0}+\binom{7}{1} = \binom{8}{1}.

Ainsi :

\binom{7}{1} = \binom{8}{1} - \binom{7}{0}.

En raisonnant modulo $8$ cela donne :

\begin{align*}
\binom{7}{1} &\equiv  0 - 1 \mod 8\\
&\equiv  -1 \mod 8.
\end{align*}

En continuant ainsi, vous obtenez tous les résidus modulo $8$ de la ligne du triangle de Pascal pour $n=7$ et constatez une alternance de $1$ et de $-1.$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=7&1 & -1 & 1  & -1  &1 &-1  &1  &-1 \\
\hline
n=8&1 & 0 & 0 & 0 & 0& 0 & 0 & 0&1\\
\hline
\end{array}

Note. Vous ignorez le dernier résidu de la ligne pour $n=7$ qui est égal à $-1.$ En prenant une autre ligne, par exemple $n=9$, vous auriez trouvé à la ligne $n=8$ un résidu de $1$ et n’auriez pas pu conclure à une absurdité.

Comme $8$ n’est pas premier, il admet un diviseur propre, à savoir un nombre $d$ compris entre $2$ et $7$, tel que $d\mid 8.$

Vous vous intéressez au coefficient binomial $\binom{8}{d} = \binom{8}{2}$ et l’exprimez avec un coefficient binomial situé dans la ligne précédente du tableau de Pascal :

\begin{align*}
\binom{8}{2} &= \frac{8 !}{2 ! 6 !}\\
&=\frac{8 \times 7 ! }{2\times 1 ! 6 !}\\
&=\frac{8}{2}\times \frac{7 !}{1 ! 6 !}\\
&= 4\times \binom{7}{1}.
\end{align*}

En prenant les résidus modulo $8$, vous obtenez :

\begin{align*}
\binom{8}{2} &\equiv 4\times (-1) \mod 8\\
&\equiv -4 \mod 8.
\end{align*}

Du coup, il vient :

0 \equiv-4 \mod 8.

Ceci est absurde.

Vous en déduisez qu’il est impossible que $8$ divise tous les coefficients binomiaux $\binom{8}{k}$ lorsque $k$ décrit l’intervalle d’entiers $\llbracket 1, 7\rrbracket.$

Traitez le cas général

Soit $n$ un entier supérieur ou égal à $2$, tel que :

\forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..

Si $n = 2$, le nombre $n$ est un nombre premier et le résultat est démontré.

Supposez maintenant que $n\geq 3.$

Alors :

\forall k\in\llbracket 1, n-1\rrbracket, \quad \binom{n}{k} \equiv 0 \mod n.

Vous allez maintenant effectuer une récurrence limitée afin de déterminer les résidus modulo $n$ des coefficients binomiaux $\binom{n-1}{k}$ lorsque $k$ décrit l’intervalle $\llbracket 0, n-1\rrbracket.$

Pour tout entier $k\in \llbracket 0, n-1\rrbracket$ vous notez $\mathscr{P}(k)$ la propriété : « le résidu modulo $n$ du coefficient binomial $\binom{n-1}{k}$ est égal à $(-1)^k$ ».

Initialisation. Pour $k=0$, vous avez d’une part $(-1)^k = (-1)^0 = 1.$

D’autre part, $\binom{n-1}{0} = 1$ donc $\binom{n-1}{0} = (-1)^0$ ce qui donne :

\binom{n-1}{0} \equiv (-1)^0 \mod n.

La propriété $\mathscr{P}(0)$ est vérifiée.

Hérédité. Soit $k$ un entier naturel inférieur ou égal à $n-2$ tel que $\mathscr{P}(k)$ soit vérifiée.

Vous avez déjà :

\binom{n-1}{k} \equiv (-1)^k \mod n.

D’après la relation de Pascal :

\binom{n-1}{k} + \binom{n-1}{k+1} = \binom{n}{k+1}.

 \binom{n-1}{k+1} = \binom{n}{k+1} - \binom{n-1}{k}.

Comme $k+1$ est un entier supérieur ou égal à $1$ et inférieur ou égal à $n-1$, vous avez :

\binom{n}{k+1} \equiv 0 \mod n.

Du coup :

\begin{align*}
 \binom{n-1}{k+1} &\equiv 0 - (-1)^k \mod n \\
&\equiv  (-1)^{k+1} \mod n.
\end{align*}

Donc la propriété $\mathscr{P}(k+1)$ est vérifiée.

Conclusion. Par récurrence limitée, il a été établi que :

\forall k\in\llbracket 0, n-1\rrbracket, \quad\binom{n-1}{k} \equiv (-1)^k \mod n.

Supposez que $n$ ne soit pas un nombre premier.

Il existe deux diviseurs propres $d$ et $d’$ c’est-à-dire deux entiers compris entre $2$ et $n-1$ tels que $n = dd’.$

Vous exprimez le coefficient binomial $\binom{n}{d}$ de la façon suivante :

\begin{align*}
\binom{n}{d} &= \frac{n ! }{d ! (n-d !)}\\
&= \frac{n}{d}\times \frac{(n-1) !}{(d-1) ! (n-d) !}\\
&=d' \times \binom{n-1}{d-1}.
\end{align*}

Maintenant, modulo $n$, vous avez :

\begin{align*}
0 &\equiv \binom{n}{d} \mod n\\
&\equiv d' \times \binom{n-1}{d-1} \mod n.
\end{align*}

Comme $d-1$ est compris entre $0$ et $n-1$, vous déduisez :

\binom{n-1}{d-1} \equiv (-1)^{d-1}\mod n.

Du coup :

0\equiv d'\times (-1)^{d-1}\mod n.

En multipliant ce résultat par $(-1)^{d-1}$ vous aboutissez à :

0\equiv d' \mod n.

Il en résulte que $n$ divise $d’$ qui est non nul, donc $n\leq d’ \leq n-1$ ce qui est absurde.

Donc $n$ est un nombre premier.

Ainsi, pour tout entier $n$ supérieur ou égal à $2$, l’implication ci-dessous est démontrée.

\boxed{n \text{ est premier }\impliedby \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Concluez

Il a été démontré l’équivalence suivante :

\boxed{\forall n\geq 2, n \text{ est premier }\Longleftrightarrow \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Prolongement

Pourriez-vous utiliser le résultat établi pour démontrer qu’un nombre entier $n\geq 2$ est premier, si et seulement si, pour tout entier $a$ premier avec $n$, $(X+a)^n\equiv X^n+a \mod n$ ?