Premiers, diviseurs et nombres parfaits
Un nombre premier ne se laisse pas partager. Toute l'arithmétique tient dans cette résistance : les premiers sont les briques, et tout entier se décompose d'une seule manière en produit de premiers. Ce qui suit part de la question la plus concrète (combien y en a-t-il, jusqu'où) et arrive à des nombres que l'Antiquité a jugés parfaits.
Le crible d'Ératosthène
Pour trouver tous les premiers jusqu'à 30, on n'en teste aucun. On écrit les nombres de 2 à 30, on garde 2, puis on raye tous ses multiples ; le premier nombre non rayé est 3, on le garde et on raye ses multiples ; puis 5 ; puis 7. Ce qui reste est la liste complète :
2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 → 10 premiers
Jusqu'à 50, on ajoute 31, 37, 41, 43 et 47 : 15 en tout.
Le crible a une propriété commode : on peut s'arrêter tôt. Pour cribler jusqu'à N, il suffit de rayer les multiples des premiers inférieurs à √N. Si un nombre composé n ≤ N avait tous ses facteurs supérieurs à √N, leur produit dépasserait N : il en a donc forcément un en dessous, et il a déjà été rayé. Pour 30, il suffit de cribler par 2, 3 et 5 : √30 vaut un peu plus de 5.
Ératosthène dirigeait la bibliothèque d'Alexandrie au IIIe siècle avant notre ère. Le même homme a mesuré la circonférence de la Terre en comparant l'ombre de midi à Syène et à Alexandrie, et s'est trompé de quelques pour cent. Ses deux procédés se ressemblent : rien qu'une observation simple, répétée avec méthode.
Les premiers se raréfient sans jamais disparaître. Il y en a 25 sous 100, 168 sous 1000, 1229 sous 10 000, soit environ un sur huit à cette hauteur, contre un sur quatre au début.
Dans le jeu : Le tamis d'Alexandrie (acte 2) · Le tamis, encore (acte 2)
Pourquoi les premiers ne s'arrêtent jamais
Supposons qu'il n'existe qu'un nombre fini de premiers, et que 2, 3, 5, 7 soient les seuls. Multiplions-les tous et ajoutons 1 :
2 × 3 × 5 × 7 + 1 = 210 + 1 = 211
Ce nombre n'est divisible par aucun premier de la liste : divisé par 2, par 3, par 5 ou par 7, il laisse toujours le reste 1. Or tout entier supérieur à 1 possède au moins un facteur premier. Donc ou bien 211 est lui-même premier (il l'est), ou bien il a un facteur premier absent de la liste. Dans les deux cas la liste était incomplète. Comme le raisonnement ne dépend pas de la liste choisie, aucune liste finie ne peut être complète : les premiers sont en nombre infini.
La preuve figure au livre IX des Éléments d'Euclide, vers 300 avant notre ère. Elle est souvent présentée comme un raisonnement par l'absurde ; Euclide, lui, la formule positivement : étant donné trois premiers, il en construit un quatrième.
Une erreur fréquente. On croit parfois que le produit des premiers plus un est toujours premier. C'est faux, et le contre-exemple arrive vite :
2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509
Ni 59 ni 509 ne figurent dans la liste de départ : la démonstration tient toujours, puisqu'elle n'affirme que l'existence d'un facteur nouveau. Mais elle ne fabrique pas des premiers à la demande, et c'est une nuance qui se perd souvent dans les résumés.
Dans le jeu : Il n'y en a pas de dernier (acte 2)
Compter les diviseurs sans les chercher
Quel est le plus petit nombre à posséder exactement six diviseurs ? On peut essayer dans l'ordre : 1 en a un, 6 en a quatre (1, 2, 3, 6), 8 en a quatre aussi. Mais il existe une règle qui répond sans essayer.
Décomposez le nombre en facteurs premiers. Un diviseur se fabrique en choisissant, pour chaque premier, l'exposant qu'on lui donne, de 0 jusqu'à son exposant maximal. Si
n = pa × qb × … alors d(n) = (a + 1)(b + 1)…
Pour obtenir six diviseurs, il faut donc écrire 6 comme un produit de tels facteurs : soit 6 = 6, ce qui donne p⁵, soit 6 = 2 × 3, ce qui donne p × q². Le plus petit de la première forme est 2⁵ = 32 ; le plus petit de la seconde s'obtient en donnant le gros exposant au petit premier : 2² × 3 = 12. Ses diviseurs sont 1, 2, 3, 4, 6 et 12.
La même règle explique pourquoi certains nombres sont si commodes. 12, 24, 60, 360 ont beaucoup de diviseurs pour leur taille (ce sont des hautement composés), et c'est la raison pour laquelle nous comptons les heures par 12 et les minutes par 60 plutôt que par 10 : 60 se partage en 2, 3, 4, 5, 6, 10, 12, 15, 20 et 30, là où 10 ne se partage qu'en 2 et 5. Le système sexagésimal des scribes babyloniens nous a survécu pour cette seule raison pratique.
Compter les multiples relève du même esprit. Combien de multiples de 7 entre 1 et 100 ? Le plus grand est 98 = 7 × 14, donc il y en a 14 : la division entière répond, on n'en énumère aucun.
Dans le jeu : Ce qui se partage (acte 1) · Elle a vu plus loin que la machine (acte 6)
Les nombres parfaits
Un nombre est parfait quand il vaut la somme de ses diviseurs propres, c'est-à-dire tous ses diviseurs, lui excepté. Le premier est 6 :
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
Après 6 vient 28, puis 496, puis 8128. Ces quatre-là étaient connus des Grecs ; le cinquième, 33 550 336, n'apparaît qu'au XVe siècle. La suite est d'une rareté extrême : on n'en connaît aujourd'hui que cinquante-et-un.
Euclide donne la recette. Si 2p − 1 est premier, alors
2p−1 × (2p − 1) est parfait
Pour p = 2 : 2 × 3 = 6. Pour p = 3 : 4 × 7 = 28. Pour p = 5 : 16 × 31 = 496. Pour p = 7 : 64 × 127 = 8128. Les nombres de la forme 2p − 1 qui sont premiers s'appellent premiers de Mersenne, et chacun fabrique un nombre parfait : les deux questions n'en font qu'une.
Deux mille ans après Euclide, Euler démontre la réciproque : tout nombre parfait pair est de cette forme. Restent les impairs, et là on ne sait rien. On a prouvé qu'un nombre parfait impair, s'il existe, dépasse 10¹⁵⁰⁰ et possède au moins dix facteurs premiers distincts. Personne n'en a trouvé, personne n'a montré qu'il n'y en a pas. C'est l'une des plus vieilles questions ouvertes des mathématiques.
Dans le jeu : La somme de ses parts (acte 2) · Ni plus, ni moins (acte 2)
Les nombres amiables
Additionnez les diviseurs propres de 220 :
1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
Faites de même avec 284, dont les diviseurs propres sont 1, 2, 4, 71 et 142 : leur somme vaut 220. Chacun désigne l'autre. On appelle un tel couple amiable, et celui-ci était connu des pythagoriciens, qui y voyaient un emblème de l'amitié : la tradition rapporte qu'on offrait des talismans gravés de ces deux nombres.
Le couple suivant, 1184 et 1210, n'a été trouvé qu'en 1866, par un lycéen italien de seize ans, Nicolò Paganini, homonyme du violoniste. Il avait échappé à Fermat, à Descartes et à Euler, qui en avaient pourtant déniché des dizaines de bien plus gros : leurs méthodes cherchaient loin et sautaient par-dessus.
Un nombre parfait est le cas dégénéré d'un couple amiable, celui où les deux membres se confondent. La même question posée sur des cycles plus longs (trois nombres qui se renvoient l'un à l'autre, puis au premier) donne les chaînes sociables, dont on connaît un cycle de longueur 28.
Dans le jeu : Deux nombres qui se répondent (acte 2)