Pour une page de jeu de son livre privé, Salomé reçoit plusieurs entiers positifs. Thomas doit leur joindre des vérifications arithmétiques, puis choisir la mention qu’il peut réellement imprimer : un contrôle est passé, un diviseur est trouvé ou la primalité est prouvée. Aucun numéro de personne, secret ou appareil n’est protégé par cette page fictive. Les nombres et les décisions appartiennent à un exercice classique. Une belle suite de restes ne donne pas davantage de renseignements parce que Thomas souhaite déjà conserver le numéro dans le livre.
La notice 351040 du Met classe l’objet parmi les livres.
La notice 351041 du Met indique les catégories albums, estampes et dessins.
La notice 351042 du Met classe l’objet parmi les livres.
Ces catégories ne fournissent aucun nombre ou contrôle. Notre page est créée, sans examen d’image ni lecture du contenu des ouvrages.
Un entier supérieur à un est premier s’il n’admet aucun diviseur positif autre que un et lui-même. Salomé reçoit d’abord 341. Thomas vérifie qu’il est impair, puis qu’il n’est divisible ni par trois ni par cinq. Il voudrait déjà l’inscrire parmi les premiers. Salomé conserve ces trois réponses sans accepter le titre : elles n’ont traité que trois diviseurs possibles. Onze multiplié par trente et un donne précisément 341. Ce produit constitue un témoin complet de composition, même si les trois premières vérifications demeurent correctes.
Le reste un peut être exact sans certifier la primalité
Thomas propose un contrôle plus long. Il prend la base deux, élève deux à la puissance 340 et regarde le reste de la division par 341. Le reste vaut un. Il voudrait remplacer sa première mention par « premier confirmé par la puissance ». Salomé garde le calcul, mais le rapproche du produit onze par trente et un. Les deux résultats sont simultanément vrais. Le contrôle à cette base est donc insuffisant pour affirmer la primalité. Elle n’efface pas le reste un parce qu’il gêne le résultat attendu ; elle retire l’implication que Thomas lui avait prêtée.
La raison d’examiner cette puissance reste valable. Pour un nombre premier p et une base a non divisible par p, la puissance a élevée à p moins un laisse le reste un. Multiplier les restes un à p moins un par a les permute : deux produits égaux modulo p auraient deux facteurs égaux, puisque a est inversible. Le produit de tous ces restes est donc inchangé. En annulant ce produit non nul, on retrouve a puissance p moins un égal à un modulo p. Thomas comprend pourquoi un échec sous ces conditions réfuterait la primalité ; le raisonnement n’a jamais dit que tous les nombres qui réussissent seraient premiers.
Salomé précise aussi la base reçue. Une base divisible par p n’appartiendrait pas aux restes inversibles de cette preuve. Thomas ne peut pas faire échouer un nombre premier en choisissant le nombre lui-même comme base, puis oublier cette restriction dans sa légende. Pour 341 avec la base deux, le problème n’est pas là : deux et 341 sont premiers entre eux. La preuve explique une condition nécessaire sous une base autorisée ; le produit onze par trente et un démontre que la condition réussie n’a pas été suffisante dans ce cas.
Pour retrouver le reste sans écrire une puissance gigantesque sur la page, Thomas garde deux valeurs : une puissance encore disponible et un produit accumulé. L’exposant restant commence à 85, la puissance disponible à deux et le produit à un. Quand l’exposant est impair, il multiplie le produit par la puissance disponible en ne gardant que le reste modulo 341. Ensuite il élève cette puissance au carré, garde son reste et divise l’exposant restant par deux en abandonnant le reste de cette division. La quantité représentée par le produit accumulé multiplié par la puissance disponible élevée à l’exposant restant ne change pas.
Pour 85, Thomas multiplie d’abord le produit par deux, obtenant deux. La puissance suivante est quatre et l’exposant restant 42 ; celui-ci est pair, donc le produit reste deux. La puissance devient seize et l’exposant 21 ; le produit devient trente-deux. Après le carré, la puissance disponible vaut 256 et l’exposant dix, sans nouvelle multiplication du produit. Au stade suivant, la puissance vaut 64 et l’exposant cinq : trente-deux fois 64 laisse le reste deux. Thomas conserve ce deux comme produit accumulé, sans le confondre avec le résultat final encore à terminer.
Les deux étapes restantes portent les exposants deux puis un. Avec deux, la puissance disponible quatre est élevée au carré sans modifier le produit. Avec un, Thomas multiplie le produit deux par seize et obtient trente-deux. L’exposant devient zéro ; le produit est alors le reste de deux puissance 85 modulo 341. Thomas peut contrôler sa trace en reprenant l’invariant à chaque ligne. Il n’a pas remplacé une multiplication exacte par une approximation décimale, et la réduction modulo 341 n’a changé aucune congruence utile aux étapes suivantes.
Les carrés intermédiaires donnent un témoin que la puissance finale cachait
Salomé observe que 340 vaut quatre fois 85, soit deux au carré multiplié par un exposant impair. Le reste trente-deux obtenu pour deux puissance 85, élevé au carré, donne un : 1024 vaut trois fois 341 plus un. Un nouveau carré conserve évidemment un. Le reste final de deux puissance 340 était donc correct, mais la chaîne a traversé trente-deux avant d’atteindre un. Salomé demande à Thomas de garder cette étape intermédiaire dans son certificat, au lieu de ne publier que la dernière case.
Si 341 avait été premier, un reste dont le carré vaut un devrait être un ou moins un modulo 341. En effet, son carré moins un est le produit de son prédécesseur et de son successeur. Un premier qui divise ce produit doit diviser l’un des deux facteurs. Ici trente-deux n’est ni un ni 340, qui représente moins un. Son carré un constitue donc un témoin de composition. Thomas peut refuser la primalité à partir de la chaîne elle-même, sans connaître d’avance onze et trente et un. Le contrôle renforcé ne dit plus seulement que la puissance finale est compatible avec un premier.
Le même reste donne ensuite les deux facteurs. Le plus grand diviseur commun de trente-deux moins un et 341 est trente et un ; celui de trente-deux plus un et 341 est onze. Le premier utilise trente et un directement, le second les nombres trente-trois et 341. Ces deux diviseurs sont strictement compris entre un et 341. Salomé les joint à la page et vérifie leur produit. Le reste intermédiaire a ainsi conduit à une factorisation affichable, pas seulement à un refus formulé comme « le test ne marche pas ».
Thomas retient alors une règle pour un entier impair n supérieur à deux. Il écrit n moins un comme un exposant impair d multiplié par une puissance de deux, deux puissance s. Il calcule d’abord le reste de a puissance d. Si ce reste est un ou n moins un, la base passe ce contrôle renforcé. Sinon, il examine les carrés successifs, au plus jusqu’au rang s moins un, en cherchant le reste n moins un. Si aucun ne l’atteint, la base donne un témoin de composition. Pour 341, d vaut 85 et s deux : trente-deux puis un ne donnent jamais 340.
La recherche de moins un a une raison sous la primalité. La puissance finale correspondant à n moins un devrait atteindre un. Si le premier reste était déjà un, la chaîne aurait satisfait ce cas initial. Sinon, juste avant sa première arrivée à un, le reste aurait pour carré un et ne serait pas un : pour un premier, il devrait donc être moins un. Thomas ne peut pas remplacer ce critère par « on a vu un à n’importe quel moment ». Une arrivée tardive à un après un reste différent des deux signes possibles est précisément ce qui a refusé 341.
Essayer toutes les bases inversibles ne sauve pas le premier contrôle
Salomé reçoit ensuite 561. Il vaut trois fois onze fois dix-sept. Thomas ne peut donc le déclarer premier, mais il veut savoir si multiplier les bases du contrôle simple finirait nécessairement par révéler le défaut. Dans ce cas, toutes les bases premières avec 561 donnent pourtant le reste un à la puissance 560. Il existe 320 restes inversibles parmi un à 560, et chacun passe ce contrôle. Salomé conserve cette propriété avec la factorisation. Même une famille complète de réussites de ce type ne prouve pas ici la primalité.
La factorisation explique ces réussites. Modulo trois, une base non divisible par trois a une puissance d’ordre deux qui vaut un ; modulo onze, sa puissance dix vaut un ; modulo dix-sept, sa puissance seize vaut un. Les trois nombres deux, dix et seize divisent 560. Une base première avec 561 a donc sa puissance 560 égale à un sous chacun des trois modules. Les facteurs trois, onze et dix-sept sont distincts et premiers entre eux : les trois divisibilités réunies font que 561 divise cette puissance moins un. Thomas n’a pas choisi seulement les bases qui l’arrangeaient pour composer le relevé de réussites.
Le compte 320 porte bien sur les bases inversibles. Parmi les 561 restes de zéro à 560, exclure les multiples de trois, onze ou dix-sept laisse deux fois dix fois seize possibilités. Les trois facteurs fournissent respectivement deux, dix et seize choix non nuls, avec une seule combinaison de restes pour chaque classe modulo 561. Thomas ne remplace pas ce nombre par 560 bases toutes autorisées. La base trois, par exemple, possède déjà avec 561 le diviseur commun trois. Salomé peut l’utiliser comme témoin de composition par ce diviseur, mais elle ne l’introduit pas dans la famille des bases inversibles pour faire paraître fausse leur réussite universelle.
Le contrôle renforcé à la base deux refuse pourtant 561. Son 560 se décompose en seize fois 35. Les restes successifs sont 263, puis 166, puis 67, puis un. Aucun n’est 560. L’arrivée à un depuis 67 expose encore une racine du carré un qui n’est ni un ni moins un. Thomas garde les deux mentions distinctes : toutes les bases inversibles passent la puissance finale du premier contrôle ; la base deux échoue au contrôle des carrés intermédiaires. Il ne dit pas que ces deux contrôles ont interrogé la même propriété en lui donnant deux noms.
À partir de 67, les diviseurs communs donnent trente-trois et dix-sept : 66 avec 561 a le diviseur trente-trois, 68 avec 561 a le diviseur dix-sept. Leur produit retrouve 561. Le trente-trois se décompose ensuite en trois fois onze. Salomé conserve ce calcul comme prolongement du témoin fourni par la chaîne. Elle ne lui donne pas un nouveau crédit de primalité pour 341 ni pour 561 ; les deux sont composés. Ce second exemple a surtout démontré une limite plus forte du premier contrôle : augmenter ses bases, même jusqu’à toutes celles de la famille autorisée, pouvait laisser la conclusion erronée entière.
Une base peut encore passer le contrôle renforcé sur un composé
Thomas souhaite maintenant imprimer « premier » dès qu’une base a satisfait la règle renforcée. Salomé lui donne 2047, qui vaut vingt-trois fois quatre-vingt-neuf. Son 2046 se décompose en deux fois 1023 : s vaut un et d 1023. À la base deux, le reste initial de deux puissance 1023 vaut un. Le contrôle accepte donc cette base immédiatement. Il n’y a pas de carré intermédiaire supplémentaire à examiner avant le rang s moins un, puisque celui-ci est zéro. La factorisation prouve néanmoins que 2047 est composé. Salomé retire la nouvelle implication universelle de Thomas.
Avec la base trois, le reste de trois puissance 1023 modulo 2047 vaut 1565. Il n’est ni un ni 2046. Comme s vaut encore un, aucun carré supplémentaire ne peut fournir le moins un recherché dans la règle. Cette base refuse donc 2047. Thomas joint les deux bases au résultat, au lieu de dire que la réussite de deux aurait invalidé le calcul de trois. Passer à une base n’imposait pas de passer à la suivante, et échouer à trois sous les conditions reçues suffit à réfuter la primalité.
Salomé ne fait pas de cette seconde base une garantie générale pour d’autres numéros. Le livre n’annonce aucun taux d’erreur, aucun tirage de bases ni aucune protection pratique. Le cas remplit une décision exacte sur 2047 : la base deux ne le séparait pas des nombres premiers, la base trois en donne un témoin, et le produit vingt-trois par quatre-vingt-neuf constitue une autre preuve de composition. Thomas conserve l’ancien contrôle passé sur sa ligne, mais sa légende finale dit « composé », avec la raison positive de ce refus. Une tentative favorable reste un renseignement exact au sein d’un résultat défavorable.
Une preuve positive peut venir d’un autre contrôle complet
Pour terminer, Salomé choisit 37. Le contrôle renforcé à la base deux écrit 36 comme quatre fois neuf. Le reste de deux puissance neuf modulo 37 vaut trente et un ; son carré vaut trente-six, soit moins un modulo 37. La chaîne satisfait donc le contrôle. Thomas vient toutefois de voir un composé passer cette même règle à une autre base. Il ne réutilise pas la seule mention « passé » pour imprimer une primalité certaine de 37. Il cherche une vérification dont le domaine entier a réellement été fermé pour ce nombre.
Si 37 était composé, il aurait un facteur supérieur à un et au plus égal à sa racine carrée. Dans un produit de deux facteurs tous deux supérieurs à cette racine, le produit dépasserait 37 ; au moins l’un doit donc rester en dessous. La racine de 37 est inférieure à sept. Un facteur premier possible dans cette plage serait deux, trois ou cinq ; quatre et six possèdent déjà un facteur premier plus petit. Thomas vérifie les trois divisions : les restes sont respectivement un, un et deux. Aucun de ces premiers ne divise 37, et aucun autre facteur premier ne peut entrer dans la plage nécessaire.
Salomé peut cette fois imprimer « premier », en associant la preuve à cette borne et aux trois divisions. Le contrôle des carrés reste conservé comme vérification supplémentaire, pas comme unique justification de la mention. Thomas n’a pas essayé tous les diviseurs jusqu’à 36, ni déclaré une recherche incomplète suffisante par fatigue. La borne lui a dit exactement où chercher un éventuel facteur ; les divisions ont fermé toutes les possibilités restantes. Cette preuve positive a une forme différente du témoin de composition donné par une base qui échoue.
Thomas répartit finalement ses quatre numéros sur la page. 341 passe la puissance finale à la base deux, mais les carrés fournissent trente-deux et les facteurs onze et trente et un. 561 passe ce premier contrôle pour toutes ses bases inversibles, mais la chaîne de deux fournit 67 et une factorisation. 2047 passe même le contrôle renforcé à deux, puis échoue à trois et possède les facteurs vingt-trois et quatre-vingt-neuf. 37 passe le contrôle renforcé et reçoit en plus la preuve bornée par les divisions deux, trois et cinq. Salomé garde les succès intermédiaires sans leur attribuer les conclusions qu’ils ne pouvaient certifier.
Un contrôle de puissance peut aussi produire une borne suffisante
Salomé donne une dernière fiche, 97, mais demande une autre preuve positive que la liste de petits diviseurs. Thomas reçoit les calculs avec la base cinq : cinq puissance 96 laisse un modulo 97, et cinq puissance 48 laisse 96. Le diviseur commun de 96 moins un et 97 est un. Il conserve ces trois conditions avec le facteur connu trente-deux de 96. Le but n’est pas de compter une réussite de plus parmi les précédentes ; il doit montrer ce que ces conditions imposent à tout facteur premier éventuel de 97.
Thomas appelle p un tel facteur premier. La base cinq reste inversible modulo p, puisque 97 n’est pas divisible par cinq. Son ordre, le plus petit exposant positif donnant un modulo p, divise 96, car la puissance 96 donne déjà un. Il ne peut pas diviser 48 : cela ferait que p divise cinq puissance 48 moins un, alors que ce nombre et 97 ont le diviseur commun un. Un diviseur de 96 qui ne divise pas 48 doit conserver tous les cinq facteurs deux de trente-deux ; s’il en manquait un, il diviserait seize fois trois, soit 48. L’ordre est donc un multiple de trente-deux. Comme p est premier, cet ordre divise aussi p moins un. Tout facteur premier p de 97 serait ainsi au moins trente-trois.
Un nombre composé possède au moins deux facteurs premiers, comptés avec leurs répétitions. Si 97 était composé, chacun de ces facteurs serait donc au moins trente-trois, et leur produit serait au moins 1089. Cela dépasse 97. Thomas obtient une contradiction et peut certifier la primalité de 97 sans essayer successivement les premiers jusqu’à sa racine. La puissance réussie a cette fois fourni une contrainte inférieure sur tous les facteurs possibles, grâce au diviseur commun vérifié et à la puissance de deux conservée dans leur ordre. Salomé imprime cette borne avec les trois conditions, plutôt que la seule ligne « puissance 96 : reste un ». Sans la borne sur les facteurs, cette dernière ligne aurait eu exactement la portée limitée déjà rencontrée sur les numéros composés.
Thomas vérifie les valeurs reçues par les carrés successifs de cinq : leurs restes pour les exposants deux, quatre, huit, seize, trente-deux et soixante-quatre sont vingt-cinq, quarante-trois, six, trente-six, trente-cinq et soixante et un. Trente-cinq fois trente-six donne le reste 96 pour l’exposant 48 ; soixante et un fois trente-cinq donne un pour 96. Salomé conserve ces calculs comme vérification des entrées du certificat. Ils ne remplacent pas l’argument qui interdit un facteur petit : ils lui fournissent les valeurs exactes à partir desquelles cet argument a fermé la demande.
Les Éditions privées donnent une forme aux voix, aux archives et aux histoires que vous souhaitez transmettre.
Découvrir Codex de Maison →