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 x=y^2. Sur cette courbe, il y aura deux types de points:

  • Pour tout i \geq 2 entier, A_i=(i^2,i).
  • Pour tout j \geq 2 entier,  B_j=(j^2,-j).

Puis on relie tous les points A_i à tous les points B_j.

Chassés-croisés

Voici la figure obtenue:

Sur l’axe des abscisses, certains points sont traversés par au moins un des segments [A_iB_j], 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 [A_iB_j] 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 [A_iB_j], puis nous montrerons que c’est un nombre composé (c’est-à-dire qui n’est pas premier).

Soit i,j \geq 2. Commençons par déterminer une équation de la droite (A_iB_j):

  1. Si i=j alors A_i et B_i ont même abscisse et donc une équation de (A_iB_j) est x=i^2 (c’est-à-dire x=ij) .
  2. Si i\neq j, le coefficient directeur a de la droite (A_iB_j) est a=\frac{(-j)-i}{j^2-i^2}=\frac{-(j+i)}{(j+i)(j-i)}=\frac{1}{i-j}. Donc une équation de la droite est y=\frac{1}{i-j}x+b où b est l’ordonnée à l’origine (qu’il nous reste à déterminer). Or, puisque A_i appartient à cette droite, b vérifie l’égalité i=\frac{1}{i-j}i^2+b donc b=i-\frac{i^2}{i-j}=-\frac{ij}{i-j} . Au final, une équation de la droite (A_iB_j) est:

y=\frac{1}{i-j} x - \frac{ij}{i-j}

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

  1. Si i=j, les coordonnées de C sont (ij;0).
  2. Si i\neq j alors, puisque l’ordonnée y de C est nulle (ce point est sur l’axe des abscisses), l’abscisse x de C vérifie 0=\frac{1}{i-j} x - \frac{ij}{i-j} donc x=ij .

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

About these ads
Ce contenu a été publié dans Arithmétique, Géométrie, avec comme mot(s)-clef(s) , , , . Vous pouvez le mettre en favoris avec ce permalien.

4 réponses à Le crible de Matiyasevitch

  1. The Dude dit :

    Ah ! J’aime bien. Et c’est esthétique !

  2. Voaary dit :

    Bravo! très bon article. Très intérressant

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s