Les Newsletters Interstices
    Niveau facile
    Niveau 1 : Facile

    Un calcul révolutionnaire

    Culture & Société
    Extraire la racine 1789-ème d'un nombre de 7 000 chiffres : un exploit « révolutionnaire » ? Cela mérite réflexion...

    Calculer la racine carrée d’un nombre n de 80 chiffres n’est pas très simple, même si on sait que l’entier n est un carré parfait (n = m2).

    Calculer la racine treizième d’un nombre n de 100 chiffres est sûrement encore plus compliqué, même si on sait que n est une puissance treizième exacte d’entier (n = m13). C’est même certainement impossible de tête.

    Que penser alors du calcul de la racine 1789-ème d’un nombre n de 7000 chiffres, même en sachant que n est une puissance 1789-ème exacte (n = m1789) ? Réussir un tel calcul de tête constituerait un exploit véritablement « révolutionnaire » !

    Pour mieux lire les 7000 chiffres du nombre proposé, affichez l’image plus grande.

    Eh bien non, cela semble paradoxal, mais le troisième exercice est le plus simple : vous pouvez d’ailleurs le faire vous-même. Le second calcul est difficile sans papier, mais quelques amateurs de calcul mental en sont capables. Le premier exercice, lui, n’est semble-t-il pas humainement possible de tête : même les plus grands calculateurs prodiges de l’histoire n’ont jamais réussi l’extraction de la racine carrée de nombres de 80 chiffres.

    Ce qui semble le plus difficile à première vue est en réalité le plus facile : c’est le paradoxe de la fausse difficulté.

    Je vous propose d’expliquer pourquoi il en est ainsi, et de découvrir la méthode permettant de calculer la racine 1789-ème d’un nombre de 7000 chiffres.

    Si vous trouvez cela trop compliqué, attaquez-vous d’abord au paradoxe lexical suivant :
    – Il est faux que la racine treizième du nombre a est le nombre b qui multiplié treize fois par lui-même donne a.

    La racine treizième du nombre a est le nombre b qui, élevé à la puissance treize, donne a, et donc… c’est le nombre qui, multiplié douze fois par lui-même, donne a.

    Alors, le calcul de la racine 1789-ème, vous y avez bien réfléchi ? Pour lire la solution, cliquez ci-dessous.

    Précisons bien à nouveau que dans les exercices mentionnés, on sait que le résultat recherché est un entier. Cela signifie que le nombre qu’on vous soumet — de 80 chiffres pour la racine carrée, de 100 chiffres pour la racine treizième, de 7 000 chiffres pour la racine 1789-ème — est la puissance exacte d’un nombre entier.

    La difficulté du problème dépend de la taille du nombre que vous devez retrouver, car c’est la quantité d’informations manquantes. La difficulté ne dépend donc pas de la longueur des données, comme on est tenté de le croire. Elle n’est pas non plus dans le fait de rechercher la racine k-ème pour un k élevé. Nous allons voir que la taille du nombre m à trouver va en décroissant d’un exercice à l’autre, et que c’est donc bien le troisième exercice qui est le plus facile.

    Commençons par lui : comment calculer la racine 1789-ème d’un nombre de 7000 chiffres ? Un petit travail d’exploration aidé d’un ordinateur montre que les seuls nombres entiers qui, élevés à la puissance 1789, donnent des entiers ayant exactement 7 000 chiffres sont :

    8171, 8172, 8173, 8174, 8175, 8176, 8177, 8178, 8179, 8180

    Les nombres inférieurs à 8171 ont une puissance 1789-ème possédant moins de 7 000 chiffres. Les nombres au-delà de 8180 ont une puissance 1789-ème possédant plus de 7 000 chiffres.

    De plus, si vous élevez 0, 1, 2, …, 9 à la puissance 1789 vous constaterez que le dernier chiffre des résultats est, dans le même ordre, 0, 1, 2, …, 9. Il en résulte immédiatement qu’en élevant à la puissance 1789 un nombre se terminant par le chiffre i, on trouve un nombre qui se termine encore par le chiffre i : le dernier chiffre d’un entier élevé à la puissance 1789 se conserve.

    Pour calculer la racine 1789-ème d’un nombre de 7 000 chiffres, il suffit donc de regarder le dernier des 7000 chiffres et d’indiquer sur la liste [8171, 8172, 8173, 8174, 8175, 8176, 8177, 8178, 8179, 8180] le nombre qui a le même dernier chiffre. Apprendre cette liste est à la portée de tout le monde, et donc tout le monde peut, de tête, extraire la racine 1789-ème d’un nombre de 7000 chiffres !

    Considérons maintenant le problème de l’extraction d’une racine treizième d’un nombre de 100 chiffres. L’ordinateur vous indique que si un nombre, élevé à la puissance 13, possède 100 chiffres alors il est compris entre les deux nombres suivants :

    41246264 et 49238826

    Si un nombre de 100 chiffres est une puissance treizième exacte, vous savez donc, sans même le regarder, qu’il commence par un 4. De plus, élever à la puissance treize ne change pas le dernier chiffre (comme pour la puissance 1789). Le travail nécessaire pour trouver la racine 13-ème d’un nombre de 100 chiffres consiste donc à déterminer les 6 chiffres manquants entre le 4 du début et le dernier chiffre facile à trouver. Quelques astuces arithmétiques rendent cela possible, et ceux qui les connaissent et s’entraînent un peu n’ont besoin que de quelques minutes voire de quelques secondes pour réaliser l’extraction de la racine treizième de nombres de 100 chiffres. L’exploit demande de l’entraînement, et peut-être même un don particulier en calcul mental, mais ce n’est pas un exploit fantastique. Il a été réalisé entre autres par Herbert de Grote, Wilhelm Klein, Gert Mittring et Alexis Lemaire.

    Les médias qui en parlent semblent victimes du paradoxe de la fausse difficulté et sans doute seraient-ils encore plus émerveillés et épatés par le génie qui réussirait le calcul « révolutionnaire » consistant à extraire la racine 1789-ème d’un nombre de 7 000 chiffres… calcul que pourtant tout le monde peut effectuer.

    Le premier exercice (extraire la racine carrée d’un nombre de 80 chiffres) est le plus difficile des trois exercices proposés. Le calcul demande en effet de retrouver 40 chiffres inconnus. Le grand mathématicien John Wallis (1616-1703) pouvait semble-t-il extraire la racine carrée de nombres de 55 chiffres. Zacharias Dase (1824-1861) pouvait extraire la racine carrée d’un nombre de 60 chiffres. Il réussit aussi l’exploit de multiplier de tête deux nombres de 100 chiffres l’un par l’autre… en 8 heures 45 minutes. À ma connaissance, personne n’a jamais pu extraire de tête les racines carrées des nombres de 80 chiffres. Les prétendus prodiges d’aujourd’hui seraient bien inspirés de s’attaquer à des exploits aussi clairs dont il est impossible de truquer la démonstration, plutôt que d’utiliser le paradoxe de la fausse difficulté pour faire passer leurs capacités pour surnaturelles.

    Notons qu’en cryptographie, de nombreux cas de fausses difficultés ont été rencontrés : quelqu’un invente un procédé de chiffrage compliqué et du fait de sa complication est persuadé qu’il s’agit d’un code inviolable… alors qu’un astucieux cryptanalyste réussit à casser le code et lit sans mal les messages secrets. Les Allemands pendant la seconde guerre mondiale étaient ainsi persuadés qu’aucune méthode ne pouvait venir à bout des messages chiffrés par la machine Enigma, dont pourtant le fonctionnement avait été élucidé – certes non sans difficulté…

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Jean-Paul Delahaye

    Professeur émérite d'informatique à l'Université des Sciences et Technologies de Lille (Lille 1) et chercheur au Centre de recherche en informatique, signal et automatique de Lille (CRIStAL).

    Voir le profil