Le crible de Matiyasevitch

Apres avoir parlé du crible d’Eratosthène dans les deux articles précédents, nous allons voir un autre crible qui est, je trouve, très esthétique. Il s’agit d’un crible dû à un mathématicien répondant au doux nom de Matiyasevitch qui est surtout connu pour avoir résolu le 10éme problème de Hilbert.

Dessine-moi une parabole

Commençons par tracer la parabole d’équation . Sur cette courbe, il y aura deux types de points:

• Pour tout entier, .
• Pour tout entier,  .

Puis on relie tous les points à tous les points .

Chassés-croisés

Voici la figure obtenue:

Sur l’axe des abscisses, certains points sont traversés par au moins un des segments , et d’autres ne sont jamais traversés. Si vous regardez de plus près, les abscisses qui ne sont coupées par aucun segment sont des nombres premiers. Nous pouvons énoncer la proposition suivante:

Un nombre situé sur l’axe des abscisses n’est pas premier si, et seulement si, un des segments traverse l’axe des abscisses en ce point.

Voici la jolie figure obtenue par Matiyasevitch himself (cliquez dessus pour l’agrandir… Elle est aussi disponible sur sa page web):

Preuve du théorème

La démarche est la suivante: nous allons d’abord déterminer les coordonnées du point d’intersection de l’axe des abscisses avec le segment , puis nous montrerons que c’est un nombre composé (c’est-à-dire qui n’est pas premier).

Soit . Commençons par déterminer une équation de la droite :

1. Si alors et ont même abscisse et donc une équation de est (c’est-à-dire ) .
2. Si , le coefficient directeur a de la droite est . Donc une équation de la droite est où b est l’ordonnée à l’origine (qu’il nous reste à déterminer). Or, puisque appartient à cette droite, b vérifie l’égalité donc . Au final, une équation de la droite est:

Si est le point d’intersection de la droite avec l’axe des abscisses alors d’après les équations que nous venons de trouver:

1. Si , les coordonnées de sont .
2. Si alors, puisque l’ordonnée de est nulle (ce point est sur l’axe des abscisses), l’abscisse de vérifie donc .

Dans tous les cas, la droite coupe l’axe des abscisses en . De là, nous pouvons prouver la propriété de ce crible: si une abscisse est coupée par une des droites , alors cette abscisse s’écrit pour certains et donc n’est pas premier. Réciproquement, si une abscisse n’est pas un nombre premier, alors il existe tels que et donc la droite traverse l’axe des abscisses en ce point.