Nombre premier : tester 997 de tête, étape par étape

Intervenant 10:00

Une très chaleureuse bienvenue dans le podcast du magazine Tangente. J'aimerais qu'on imagine une scène pour commencer.

Intervenant 20:06

Vas-y, je

Intervenant 10:07

t'écoute. Voilà, on est coincé dans les embouteillages, la routine quoi, et on a le regard fixé, un peu distraitement, sur la plaque d'immatriculation de la voiture de devant.

Intervenant 20:17

Ouais, le truc qu'on a tous déjà fait.

Intervenant 10:19

Grave. Et là, on lit un nombre, genre 997. Pour la plupart des gens, c'est juste une simple suite de chiffres, peut-être vaguement familières.

Intervenant 20:29

Un identifiant, quoi.

Intervenant 10:31

Exactement. Mais pour un esprit un peu curieux, c'est une invitation. La question qui tue. Ce nombre est-il premier ?

Intervenant 20:38

Ah, la fameuse question.

Intervenant 10:40

Voilà. Et c'est justement le titre d'un article source absolument fascinant sur lequel on se penche aujourd'hui. L'objectif de cette discussion approfondie, c'est pas du tout de faire un cours magistral pesant.

Intervenant 20:51

Non, au contraire, ce serait mortel.

Intervenant 10:53

C'est ça. On veut plutôt transformer une tâche qui semble relever de la calculatrice humaine, donc trouver si un nombre est premier de tête, en un vrai jeu de pistes ludique et hautement créatif.

Intervenant 21:03

Et surtout, il faut bien préciser que les mathématiques qu'on va aborder ici, elles sont accessibles à tout le monde.

Intervenant 11:09

Absolument. Tout en gardant une rigueur totale. Parce que pourquoi s'embêter à faire ça de tête au fond ? Parce que c'est une gymnastique mentale jubilatoire. C'est une façon de redécouvrir les nombres de notre quotidien sous un tout nouveau jour. Bon, décortiquons tout ça. Par où on commence ?

Intervenant 21:24

Avant de jouer avec les nombres et de faire des acrobaties, il faut définir les règles du jeu. Et surtout, comprendre pourquoi la méthode qu'on appelle brute est vouée à l'échec.

Intervenant 11:33

D'accord. Un rappel des bases s'impose.

Intervenant 21:36

Et c'est un entier strictement supérieur à 1 qui ne se divise que par 1 et par lui-même.

Intervenant 11:41

Donc c'est un peu un atome indivisible des maths en fait.

Intervenant 21:44

Exactement. Et la méthode naïve pour le vérifier, ce serait d'utiliser la bonne vieille division euclidienne. Tu divises par deux, puis par trois, puis par quatre, jusqu'à arriver à ton nombre moins un.

Intervenant 11:55

Ouais, en espérant ne jamais tomber sur un contron. Mais très honnêtement, de tête, c'est insoutenable.

Intervenant 22:01

Le cerveau humain va vite saturer, clairement. Historiquement, on a compris ce problème très tôt. Il y a le fameux crible d'Eratosthène, par exemple.

Intervenant 12:10

Eratosthène, c'était le directeur de la grande bibliothèque d'Alexandrie dans l'Antiquité, non ?

Intervenant 22:14

C'est ça. Un gars qui correspondait régulièrement avec Archimède, rien que ça.

Intervenant 12:19

Pas mal le carnet d'adresses, ouais. Son idée, si je me souviens bien, c'est très visuel. On écrit tous les nombres jusqu'à 100, disons. On entoure le 2 qui est premier, puis on ré-directe tous les multiples de 2.

Intervenant 22:30

Ouais, tous les nombres pairs du coup.

Intervenant 12:32

Puis on passe au premier nombre pareillé, le 3, on l'entoure et bim, on règle tous ces multiples. Et on continue comme ça. À la fin, les nombres qui n'ont pas été barrés, ce sont les nombres premiers.

Intervenant 22:43

C'est super élégant pour créer une liste. Mais comme le souligne l'article, face à une plaque d'immatriculation dans la rue, tu ne vas pas commencer à tracer une grille sur ton pare-brise.

Intervenant 12:52

C'est clair. Il nous faut un filtre plus rapide.

Intervenant 22:54

Ce qui nous amène au vrai moment de grâce mathématique, la règle de la racine carrée. Au lieu de tester jusqu'à notre nombre moins 1, on s'arrête à la racine carrée du nombre, disons n.

Intervenant 13:06

Attends, la racine carrée, pourquoi on s'arrête là ?

Intervenant 23:09

Qu'il est égal à un nombre p multiplié par un nombre q. Or ces deux facteurs ne peuvent pas être tous les deux supérieurs à la racine carrée de n.

Intervenant 13:18

Ah, parce que sinon, si on les multiplie, le résultat sera forcément plus grand que N.

Intervenant 23:22

Voilà. Si N vaut 100, la racine, c'est 10. Si tu as deux diviseurs qui sont, je ne sais pas, 11 et 12, 11 x 12, ça fait 132 passants. Ouais,

Intervenant 13:32

c'est imparable. En gros, pour donner une image, c'est comme si on cherchait un objet caché dans un immense manoir à plusieurs étages. Mais grâce à une petite astuce logique, on arrive à prouver que l'objet, s'il existe, ne peut se trouver que dans les pièces du rez-de-chaussée.

Intervenant 23:45

C'est une excellente analogie.

Intervenant 13:47

Du coup, le champ de recherche est instantanément réduit. Par exemple, pour un nombre à deux chiffres, le max, c'est 99. La racine de 100, c'est 10. Donc, notre rez-de-chaussée, c'est juste les nombres premiers inférieurs à 10. Le 2, le 3, le 5 et le 7.

Intervenant 24:03

Juste quatre nombres à tester. Et pour notre fameuse plaque d'immatriculation à trois chiffres, donc en dessous de 1000 ?

Intervenant 14:09

La racine de 1000, 30 x 30, ça fait 900. 31 x 31, c'est 961. 32, ça dépasse. Donc on teste jusqu'à 31.

Intervenant 24:18

C'est qui nous donne 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 et 31. On passe de 1000 divisions potentielles à

Intervenant 14:31

1. C'est fou quand on y pense. Mais bon, 11 divisions de tête, pour certains de ces nombres, ça reste un peu volu, non ?

Intervenant 24:37

C'est là que l'article devient génial.