Sur nombres premiers et problèmes de classe P

Source : un article très détaillé de la revue Quadrature n°60 (avril-juin 2006).

Il vient d'être démontré (août 2002) que le problème de savoir si un entier naturel n est un nombre 1er est un problème qui appartient à la classe P, c'est-à-dire :

1) on peut y répondre par oui ou par non
2) il peut être résolu par un algorithme déterministe et en un temps polynomial
3) cela pour tout entier n

Cette découverte a été faite par le professeur Agraval de L'Institut Indien de Technologie à Kanpur et deux de ses élèves Kayal et Saxena, d'où l'algorithme AKS.

Comme quoi, on peut encore trouver des choses en mathématiques...

Cette découverte repose (entre autres) sur la propriété suivante :

Soit n dans N avec n³2 : n est un nombre 1er si et seulement si
n divise les coefficients binômiaux C(n,p)=n(n-1)...(n-p+1)/p!, pour pÎ{1,2,...,n-1}.

Ce résultat se constate de façon immédiate sur les premières lignes du triangle de Pascal :

1 2 1
1 3 3 1
1 4 6 4 1
1 51010 5 1
1 6152015 61
1 72135352171

La démonstration n'est pas très difficile :
--pour le sens gauche-droite on la trouve partout : il est en effet bien connu que pC(n,p)=nC(n-1,p-1), pour i=1,2,..,n et donc n divise pC(n,p) ; si n est 1er, pour pÎ{1,2,...,n-1}, n est alors 1er avec p et donc d'après le thérème de Gauss il divise C(n,p).
--pour le sens droite-gauche, on la voit moins souvent.

Voici tout d'abord la preuve de Quadrature :

soit d un diviseur de n avec 1£d£n-1 : on va montrer que d=1, et donc n sera un nombre 1er.
On a dC(n,d)=nC(n-1,d-1), soit C(n,d)=kC(n-1,d-1) avec k=n/d qui est un entier.
Par hypothèse n divise C(n,d), donc n divise kC(n-1,d-1), c'est-à-dire kC(n-1,d-1) congru à 0 modulo n, ce qui s'écrit kC(n-1,d-1)º0 (n), (voir par exemple le début de ma page sur codage affine) ; en effet pour ce qui suit il va être plus pratique de travailler modulo n.
Par récurrence montrons que pour iÎ{1,2,...,n-1} on a C(n-1,i)º(-1)i (n) : c'est vrai si i=1 puisque C(n-1,1)=n-1º-1 (n)
supposons la propriété vraie jusqu'au rang i£n-2 :
en utilisant la formule qui permet de construire le triangle de Pascal, à savoir :
C(n-1,i)+C(n-1,i+1)=C(n,i+1) et comme C(n,i+1)º0 (n), car i+1£n-1, on obtient (-1)i+C(n-1,i+1)º0 (n), soit C(n-1,i+1)º(-1)i+1 (n), et la propriété est bien vraie au rang i+1. En particulier on a C(n-1,d-1)º(-1)d-1 (n), soit kC(n-1,d-1)ºk(-1)d-1 (n) ; mais on a vu que kC(n-1,d-1)º0 (n), donc k(-1)d-1º0 (n), ce qui veut dire (puisque (-1)d-1 est égal à -1 ou 1) que n divise k=n/d, donc n£n/d, soit d£1 et finalement d=1, et n est bien un nombre 1er.

Et voici une autre démonstration, sans modulo :

supposons n non premier : il admet alors un diviseur (strict) d qui est un nombre premier et n=kd, avec k entier et 1<d<n.
On a alors C(n,d)=C(kd,d)=(kd)(kd-1)(kd-2)...(kd-d+1)/d! et donc
(d-1)!C(n,d)=k(kd-1)(kd-2)...(kd-d+1) ; mais par hypothèse n=kd divise C(n,d), puisque 1<d<n, et ainsi d divise le produit de facteurs (kd-1)(kd-2)...(kd-d+1) ; mais d étant 1er, il doit diviser un de ces facteurs, ce qui est impossible puisque chaque facteur de ce produit est de la forme kd-k', avec k' non divisible par d puisque k' est dans {1;2;...;d-1}. On obtient ainsi une contradiction et n est donc forcément un nombre 1er. En fait la propriété précédente est utilisée sous la forme suivante : Soient a dans Z et n dans N avec n³2 et pgcd(n,a)=1 : n est un nombre 1er si et seulement (X+a)nºXn+a (n)
(c'est-à-dire les coefficients respectifs des polynômes (X+a)n et Xn+a sont égaux modulo n, c'est-à-dire tous les coefficients du polynôme (X+a)n-Xn-a sont divisibles par n).
La preuve est immédiate à partir du résultat précédent, et compte tenu du théorème de Fermat ( si n est un nombre 1er, alors anºa (n), pour tout a dans Z ). Par ailleurs la démonstration de la validité de l'algorithme AKS utilise aussi la notion de polynômes cyclotomiques sur les corps finis.

Cette démonstration est détaillée dans l'article de Quadrature ; inutile de dire que beaucoup de choses me dépassent, cela malgré le fait, et là je cite toujours Quadrature, que cette démonstration ne nécessite que quelques outils assez simples d'algèbre, ce qui est loin d'être le cas des autres algorithmes de primarité qui font appel à des résultats très pointus en théorie des nombres.

Je termine par quelques extraits de leur conclusion :
cet algorithme demeure de nos jours inutilisable en pratique à grande échelle, mais à la lueur de sa démonstration, on peut se demander si d'autres résultats mathématiques dont la démonstration nous échappe encore, ne posséderaient pas une preuve aussi brillante, élégante et simple.