346. Un nombre est premier, si et seulement si, il divise tous les coefficients binomiaux de sa ligne dans le tableau de Pascal, excepté le premier et le dernier

Le but de ce contenu 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\comma$ le coefficient binomial $\binom{n}{k}$ est divisible par $n.$

Visualisez le triangle de Pascal

Les premières lignes du triangle 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\comma$ vous constatez que les coefficients binomiaux $7\comma$ $21\comma$ $35\comma$ $35\comma$ $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\comma$ ce qui s’écrit ainsi :

6 \nmid \binom{6}{3}.

Autrement dit :

\exists k\in\llbracket 1, 5\rrbracket, \quad 6 \nmid \binom{6}{k}.

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}\comma$ le lemme d’Euclide, dont une démonstration figure dans un autre article, 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\comma$ du produit $k! (n-k)!.$ Comme $k$ est compris entre $1$ et $n-1\comma$ 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.$

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 126.

Or, le fait que $n$ divise $i$ avec $i$ non nul impose d’avoir $n\leq i.$ Comme il a été vu que $i \leq n-1\comma$ vous aboutissez à 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\comma$ 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\comma$ 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\comma$ 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. Le dernier résidu obtenu pour la ligne $n=7\comma$ à savoir $-1\comma$ ne coïncide pas avec $\binom{7}{7}=1.$ Cela fournirait déjà une contradiction ici, mais uniquement parce que $8$ est pair. Pour un entier impair, par exemple $n=9\comma$ vous auriez trouvé à la ligne $n=8$ un dernier résidu égal à $(-1)^8=1\comma$ qui coïncide avec $\binom{8}{8}\comma$ et n’auriez pas pu conclure à une absurdité. Ce dernier résidu n’est donc pas utilisé.

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

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 triangle 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\comma$ vous obtenez :

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

Comme $\binom{8}{2}\equiv 0 \mod 8\comma$ 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\comma$ tel que :

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

Si $n = 2\comma$ 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 coefficients binomiaux $\binom{n-1}{k}$ modulo $n$ lorsque $k$ décrit l’ensemble $\llbracket 0, n-1\rrbracket.$

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

Initialisation. Pour $k=0\comma$ 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}.

Donc :

\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\comma$ 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’\comma$ c’est-à-dire deux entiers compris entre $2$ et $n-1\comma$ 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, comme $d$ est compris entre $1$ et $n-1\comma$ modulo $n\comma$ 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\comma$ 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}\comma$ et comme $(-1)^{2(d-1)} = 1\comma$ 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\comma$ 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\comma$ l’égalité $(X+a)^n\equiv X^n+a \mod n$ est vérifiée dans l’anneau des polynômes ?