Archives pour la catégorie Énigmes

Jeter le masque ?

La seule méthode de chiffrement démontrée inviolable est le masque jetable … dont il est impératif qu’il soit jeté après un seul usage. Avant d’expliquer pourquoi, il nous faut dire de quoi il s’agit.

Chiffrement par substitution

La méthode de substitution la plus ancienne est attribuée à Jules  César, elle consiste à décaler les lettres du message d’un certain nombre. Si on choisit un décalage d’une lettre, “cesar” devient “dftbs”. Pour un décalage de deux lettres, nous obtenons “eguct” et ainsi de suite. On peut complexifier ce chiffrement en changeant de décalage à chaque lettre, la suite de décalages est la clef de chiffrement. Si on utilise l’alphabet latin (de A à Z), qu’on peut assimiler aux nombres de 0 à 25, ce la donne.

 

Clair V O I C I L E C L A I R
Clef C E L A E S T L A C L E
Chiffré X S T C M D X N L C T V

 

Chaque décalage correspond à une addition. Pour la première colonne V + C correspond à 21 + 2 = 23 soit X et ainsi de suite. Quand on obtient un nombre supérieur ou égal à 26, on lui retranche 26. Par exemple, à la sixième colonne, L + S correspond à 11 + 18 = 29 reste 3 d’où L + S = D.

Le masque jetable

Plus la clef est longue plus ce chiffre par substitution poly-alphabétique est difficile à décrypter. En 1917, Gilbert Vernam en conclut que l’idéal était que la clef soit aussi longue que le message. Joseph Mauborgne remarqua plus tard qu’il valait mieux qu’elle soit aléatoire et par voie de conséquence qu’on ne l’utilise qu’une fois. En 1949, en créant la théorie de l’information, Claude Shannon démontra que ce chiffre était inviolable. C’est le seul dont on ait démontré qu’il soit indécryptable.

Claude Shannon et une de ses créations : la souris qui sort seule d’un labyrinthe.

Les mésaventures des Soviétiques

Les Soviétiques firent l’erreur d’utiliser deux fois la même clef dans les années 1930 d’après les archives britanniques. Ils persistèrent dans leur erreur après la guerre ce qui facilita le projet Venona américain de décryptement des messages des services de renseignements soviétiques. Trois mille messages furent ainsi décryptés totalement ou partiellement. Une des conséquences a été la détection d’espions soviétiques comme les époux Rosenberg et les cinq de Cambridge dont le célèbre agent double Kim Philby. Cette faiblesse du masque jetable, que Claude Shannon a montré inviolable rappelle la différence entre théorie et pratique et surtout qu’un théorème de mathématiques a des hypothèses strictes, ici le côté aléatoire des clefs et leur utilisation unique. On ne peut l’utiliser en dehors de ses conditions d’application, même si la question est tentante pour qui ne domine pas ces questions.

La faille …

Si on utilise deux fois la même clef, il suffit de faire la différence des deux chiffrés pour faire disparaître la clef. Plus précisément, on obtient le premier message chiffré avec une clef liée au second message. On utilise alors la méthode du mot probable pour décrypter le tout.

Les vestiges de la base vingt

La façon de dire les nombres en français a des variantes locales. Ainsi comment doit-on lire, ou écrire en toutes lettres, le nombre 283 ? La logique du français voudrait : deux cent huitante-trois… pourtant cela ne s’écrit ainsi que dans certaines régions de l’Est de la France et dans quelques cantons suisses. Les Belges préfèrent : deux cent octante-trois et la majorité des Français, comme des Canadiens : deux cent quatre-vingt-trois.

Un ancien usage ?

Ces quatre-vingts viendraient d’une ancienne façon de compter en usage autrefois en France et dont nous aurions hérité des Celtes. En effet, on la retrouve en Bretagne comme au pays de Galles et en Irlande. Le principe est partout le même, il s’agit d’un usage partiel de la base vingt. Il nous en reste le quatre-vingts de nos comptes mais aussi un hôpital parisien : celui des Quinze-Vingts, fondé par saint Louis (1214 – 1270) pour accueillir 15 fois 20, c’est-à-dire 300, vétérans aveugles. Il est toujours spécialisé en ophtalmologie. Cette façon de compter se retrouvait autrefois plus souvent qu’aujourd’hui, ainsi, dans L’avare de Molière, à la scène 5 de l’acte II, Frosine dit à Harpagon :

Par ma foi ! Je disais cent ans ; mais vous passerez les six vingts.

Six vingts signifiait 120. Pour 100 cependant, Frosine ne dit pas cinq vingts. Dans Notre-Dame de Paris, Victor Hugo (1802 – 1885) nous fait découvrir une autre trace de ce système quand il relate l’assaut de Notre-Dame par les truands (au livre X, chapitre 4) :

Clopin Trouillefou, arrivé devant le haut portail de Notre-Dame, avait en effet rangé sa troupe en bataille. Quoiqu’il ne s’attendît à aucune résistance, il voulait, en général prudent, conserver un ordre qui lui permît de faire front au besoin contre une attaque subite du guet ou des onze vingts.

Au Moyen-Âge, les onze vingts étaient un corps de police de 11 fois 20, c’est-à-dire 220, membres. Cet usage de compter par vingtaines était alors plus général que le montre ces quelques vestiges, comme Charles-Pierre Girault-Duvivier (1765 – 1832) le note dans sa grammaire des grammaires :

Six vingts vieillit ; on dit plus ordinairement cent-vingt ; on disait encore dans le siècle passé sept vingts ans, huit vingts ans : depuis six ou sept vingts ans que l’église calvinienne a commencé (Bossuet) – Des femmes enceintes au nombre de huit vingts et plus – l’Académie ne condamnait pas autrefois cette manière de s’exprimer, et en permettait l’usage jusqu’à dix-neuf vingts en excluant seulement deux vingts, trois vingts, cinq vingts et dix vingts.

Une fois admis ce compte particulier en vingtaine pour la quatrième, il est logique de continuer jusqu’au seuil de la cinquième, c’est-à-dire jusqu’à 99. Nonante est ainsi devenu quatre-vingts dix, écrit depuis quatre-vingt-dix. En revanche, en Belgique, 90 est resté nonante sauf pour parler du roman de Victor Hugo : Quatre-vingt Treize. Une étrangeté reste et concerne le pluriel mis à vingt. On écrit quatre-vingts mais quatre-vingt-un et non quatre-vingts et un comme le voudrait l’imitation des cas de vingt à soixante, de plus vingt perd son pluriel et se trouve au singulier alors que le nombre a augmenté !

Septante ou soixante-dix ?

 

Quatre-vingts s’explique par la concurrence entre deux systèmes de numération, l’un fondé sur la dizaine et l’autre sur la vingtaine. Soixante-dix n’a pas la même raison de remplacer le logique « septante » comme il est utilisé en Belgique, en Suisse et dans l’Est de la France. Plus de vestige d’une base vingt ici. D’où vient cette exception culturelle ?

Plusieurs explications concernent Louis XIV (1638 – 1715). Selon une première version, le Roi-Soleil ne supportait pas l’idée de quitter la soixantaine pour devenir septuagénaire. Sa mégalomanie lui aurait fait décider que l’on dirait dorénavant soixante-dix et non septante. Dans une autre version, le soleil déclinant aurait perdu tant de batailles dans les années septante, octante et nonante qu’il aurait banni ces mots du vocabulaire… Ces histoires peuvent séduire, mais leur authenticité est douteuse. La seule certitude est que soixante-dix, quatre-vingts et quatre-vingt-dix sont apparus au cours du XVIIe siècle, celui de Louis XIV. Claude Favre de Vaugelas (1585 – 1650) en donne la preuve quand, dans Remarques sur la langue françoise utiles à ceux qui veulent bien parler et escrire, il écrit :

Septante, n’est Français qu’en un certain lieu où il est consacré, qui est quand on dit la traduction des Septantes […]. Hors de là il faut toujours dire soixante-dix, tout de même que l’on dit quatre-vingts et non pas octante ou quatre-vingts dix et non pas nonante.

Vaugelas cite ici la traduction de la Bible hébraïque en grec, dont la lecture du livre XII des Antiquités judaïques de Flavius Josèphe (37 – 100 environ) explique le nom de Septante. Selon cet auteur, Ptolémée II Philadelphe (309 – 246 avant Jésus-Christ), roi d’Égypte, aurait demandé à Éléazar, grand prêtre des Juifs (à Alexandrie), d’envoyer six anciens de chaque tribu traduire les textes hébraïques. Il conclut étrangement par :

Je ne crois pas nécessaire de donner les noms des septante anciens envoyés par Éléazar.

Pourtant, les tribus d’Israël étant au nombre de 12, les traducteurs auraient dû être 72 (6 x 12). Volonté d’arrondir un nombre qui n’est sans doute qu’un mythe ? Erreur de calcul ? Nous ne saurons jamais, mais nous devons sans doute à Flavius Josèphe l’appellation de Septante donnée à la traduction grecque de l’Ancien Testament. Dans tous les cas, l’article de Vaugelas montre qu’avant lui, 70 se disait communément septante.

Pour suivre ses recommandations, l’Académie française recommanda l’usage des expressions soixante-dix, quatre-vingts et quatre-vingts dix. La raison invoquée par Vaugelas n’est motivée que par l’affirmation : « ce n’est pas français », ce qui ressemble fort à un argument d’autorité. Pourquoi ces choix ? La réponse est sans doute à lire dans les nouveaux éléments d’arithmétique de Thomas Fantet de Lagny (1660 – 1734), un mathématicien de l’époque :

La raison de cette irrégularité peut être attribuée vraisemblablement à l’agrément de la prononciation que l’on trouve plus douce dans ce mot, par exemple, soixante-dix que dans septante, à cause des deux consonnes pt, que notre langue évite, et par la même raison, on a mieux aimé dire quatre-vingts qu’octante, comme on disait autrefois à cause des deux consonnes ct, […] quoiqu’il en soit, les arithméticiens ont eu raison de retenir les mots de septante, octante et nonante […] car on est porté à écrire 7, 8 et 9 […] et non 6 et 4.

Bien qu’il ne soit guère convaincant en ce qui concerne le bannissement des sons « pt » ou « ct » puisqu’il ne semble que jamais des mots comme « opter » ou « octave » n’aient été inquiétés, l’argument des académiciens paraît bien se situer au niveau de l’élégance, de la musique et de la douceur des sons. Cependant, pour éviter les confusions, du temps où elles existaient encore, c’est-à-dire jusqu’en 1987, les criées à la Bourse de Paris se faisaient en suivant l’ancien compte. En effet, soixante-dix-neuf porte à noter un 6 pour commencer alors que septante-neuf ne prête à aucune confusion.

 

Le salon de la culture et des jeux mathématiques 2020

Depuis l’an 2000, fin Mai, place saint Sulpice à Paris le salon de la culture et des jeux mathématiques se propose de présenter les mathématiques sous forme tout à la fois ludique et utile. Il attire ainsi chaque année de l’ordre de 20000 personnes, élèves, étudiants, professeurs, parents et passants.

Vue d’une allée du salon

Cette année 2020, la crise sanitaire a mené à son interdiction. Les organisateurs ont décidé de le dématérialiser. Il est donc ici : http://salon-math.fr/ du 28 au 31 Mai.

Comme chaque année, j’y suis responsable d’un stand dédié à la cryptologie et à la cybersécurité, celui de l’ARCSI (association des réservistes du chiffre et de la sécurité de l’information) dont je suis administrateur.

Ci-dessus, j’explique le fonctionnement d’une C-36, machine à chiffrer française de la Seconde Guerre mondiale à Cédric Villani sous l’œil bienveillant du général Jean-Louis Desvignes, président de l’ARCSI.

Nous y organisons des visio-conférences dont la liste et les horaires se trouvent en ligne de même que quelques curiosités et énigmes. Personnellement, j’en donne quatre :

28 Mai 10H-10H 30 Les correspondances personnelles chiffrées du Figaro en 1890
29 Mai 11H-11H 30 La faiblesse du chiffre de l’armée napoléonienne
30 Mai 11H-11H 30 Le chiffre de Marie-Antoinette
31 Mai 11H-11H 30 Les erreurs de cybersécurité sont avant tout humaines

Sur l’espace rencontre du salon en 2019.

(Henri) Quatre sur (le pont) Neuf

Prenez un mot de neuf lettres, comme « minutieux », brouillez-les, vous obtenez par exemple XNIIMTUEU. Écrivez-le dans ce nouvel ordre dans un carré 3 par 3 :

Une grille de quatre sur neuf.

Nous avons ainsi formé une grille de notre jeu quatre sur neuf. Le but est maintenant de trouver un maximum de mots français de quatre lettres contenant la lettre centrale (en bleu, ici M) en un minimum de temps. Les accents ne comptent pas, ainsi mute et muté sont considérés comme le même mot.

Si on commence par les mots dont la première lettre est M, nous trouvons rapidement : mite, mine, mixe, mute, muni, muet, meut, etc. Nous pouvons continuer en essayant de placer M dans une autre position : émut, etc.

Quelle est la meilleure stratégie possible ? Chacun la sienne sans doute mais le jeu demande manifestement des qualités de lecture d’un pavé de trois lettres sur trois. Comment voir les chemins intéressants ? Il demande aussi de considérer les digrammes selon leurs fréquences. Par exemple, ici, « en » et « un » sont fréquents donc à considérer pour gagner du temps.

Combien existe-t-il de solutions pour cette grille ? La question est ouverte et la réponse dépend du dictionnaire utilisé. Peut-on trouver une grille sans solution ? Avec une seule ? Deux, etc. ? Toutes ces questions sont ouvertes cher lecteur… et attendent vos réponses. On comprendra, par exemple, que de partir d’un mot de neuf lettres assure la présence de lettres, digrammes et trigrammes relativement fréquents… et donc augmente le nombre de solutions.

Pour vous exercer

Il est facile de créer d’autres grilles, et de même de créer un logiciel pour jouer à ce jeu en français.

On part d’une liste de mots de neuf lettres (il en existe plus de 50 000), d’un générateur de permutations aléatoires d’un ensemble à neuf éléments puis d’un dictionnaire pour vérifier les solutions trouvées. Il reste à ajouter une horloge pour augmenter le stress du joueur. Attention avant de créer ce jeu : il est hautement addictif et son abus peut provoquer de graves ennuis de santé !

Le postulat d’Euclide et la courbure de l’espace

Dans Les Eléments, Euclide pose plusieurs axiomes et définitions de la géométrie plane puis démontre un certain nombre de théorèmes. Entre les deux, il postule que, par un point donné, il passe une et une seule parallèle à une droite donnée. En apparence, il s’agit d’un théorème sans preuve. Des générations de mathématiciens ont essayé de le démontrer sans jamais y arriver. Avant d’analyser la question, il est nécessaire de revenir sur les axiomes d’Euclide.

Les axiomes d’Euclide

Il serait fastidieux de passer en revue les axiomes et les définitions de la géométrie plane d’Euclide. Pour en comprendre l’origine, il suffit de revenir au mythe de la caverne, une allégorie où Platon estime que le monde réel est rempli d’objets dont les modèles sont ailleurs, dans le monde des idées. De la même façon, les points, droites et angles d’Euclide sont les idées des points, droites et angles réels tels qu’un maçon les utilise. Qu’est-ce qu’une droite ? Pour le comprendre, faites comme le maçon. Prenez une corde et deux piquets. Plantez les deux piquets et tendez la corde. Vous réalisez ainsi le plus court chemin entre eux.

En tendant une corde entre deux piquets, on obtient une droite.

Avec la même méthode et trois piquets, vous fabriquez un triangle donc trois angles.

En tendant une corde entre trois piquets, on obtient un triangle Mesurez les angles et faites-en la somme. Comme vous connaissez déjà le résultat, vous trouverez 180°.

Une preuve sous condition

Une petite figure suffit pour démontrer ce résultat. Pour la tracer, en plus de notre corde et de nos piquets, munissons-nous d’un rapporteur capable de reporter un angle donné le long d’une droite, en un point.

Considérez un triangle ABC, prolongez le côté AB en BE et du point B, en utilisant le rapporteur, portez la droite BD de sorte que l’angle CBD soit égal à l’angle ACB (en rouge tous les deux). De même, portez la droite BD’ de façon que l’angle EBD’ soit égal à l’angle BAC (en bleu).

En B, on reporte les angles en rouge et en bleu, on obtient deux droites BD et BD’. D’après le postulat d’Euclide, ces droites sont confondues. Les angles du triangle ABC se retrouvent donc en B et forment un angle plat c’est-à-dire 180°.

Les droites BD et BD’ sont parallèles à la droite AC (les angles rouges et jaunes sont alternes internes). Elles sont donc identiques puisque, d’un point, on ne peut tracer qu’une parallèle à une droite donnée. Les trois angles du triangle ABC se reportent ainsi en B pour former un angle plat, c’est-à-dire 180°. Nous avons ainsi démontré que la somme des angles d’un triangle est égale à 180° … si le postulat d’Euclide est vrai.

L’idée qui dépostule

Quand on dessine la figure précédente sur une feuille de papier, les droites BD et BD’ sont confondues. Coupons le papier le long de la demi-droite BD et déplaçons BD’ sur BD, la feuille se courbe. Elle devient comme un sommet de montagne et la somme des angles du triangle, supérieure à 180°. Au contraire, en écartant BD’ de BD, la feuille se courbe dans l’autre sens. Elle devient comme un col de montagne et la somme des angles du triangle, inférieure à 180°.

Triangle sur la sphère

Pour développer cette idée, reprenons les axiomes d’Euclide sans le postulat en nous plaçant avec nos piquets, notre corde, notre rapporteur et nos définitions sur une sphère. Le plus court chemin entre deux points est obtenu en suivant l’arc de grand cercle entre eux.

Ligne droite sur une sphère.

Sur une sphère, deux grands cercles se coupent toujours. Autrement dit, deux droites ne sont jamais parallèles ! Le postulat d’Euclide y est faux et notre démonstration lumineuse aussi. Dans ce cas, les deux droites BD et BD’ ne se recoupent pas, l’angle DBD’ n’est pas nul. La somme des angles du triangle est donc supérieure à 180°. Pour vous en convaincre davantage, prenez un globe terrestre miniature, deux points sur l’équateur et dessinez le triangle formé avec l’un des pôles. La somme de ses angles est égale à 180° plus l’angle au pôle, elle est donc strictement supérieure à 180°.

Triangle sur une sphère. En mesurant ses angles, on montre que leur somme est supérieure à 180°.

Triangle sur une selle de cheval

Si nous nous plaçons sur une surface différente comme un col de montagne ou une selle de cheval, la somme des angles d’un triangle devient inférieure à 180°. Sur la figure de notre démonstration, les droites BD et BD’ se couvrent.

Un triangle sur une selle de cheval.

Les surfaces comme les plans, les cylindres ou les cônes où la somme des angles d’un triangle est égale à 180° sont dites de courbure nulle, celles comme la sphère ou les ellipsoïdes où la somme des angles est supérieure à 180°, de courbure positive et celles comme la selle de cheval où la somme des angles est inférieure à 180°, de courbure négative. Ces surfaces ne sont pas des plans euclidiens.

Aire d’un cercle

De même, grâce à un piquet et une corde, sur toute surface, nous pouvons tracer un cercle de rayon R. Si la courbure de la surface est nulle, son aire est égale à p R2. Si elle positive, elle est inférieure, sinon elle est supérieure.

Courbure d’un espace

Notre vision en trois dimensions nous permet d’admettre facilement ces résultats. Imaginons des êtres plats « collés » sur une surface de dimension deux pour lesquels, elle serait l’univers entier. Incapable d’en sortir, il ne verrait pas sa courbure. Il pourrait cependant tracer un triangle, mesurer ses angles et déterminer ainsi si son univers a une courbure positive, négative ou nulle.

De même, un extraterrestre vivant et voyant dans un monde en dimension quatre pourrait « voir » la courbure de notre univers. Nous y sommes trop englués pour cela. Le même phénomène existe pourtant et nous pouvons le tester : il suffit de mesurer le volume d’une sphère ou la somme des angles d’un triangle. Jusqu’à présent, les mesures effectuées font penser que notre univers est de courbure quasiment nulle.

Le carré Luoshu

La première référence à un carré magique est une légende chinoise associée à la rivière Luohe, un affluent du fleuve Jaune, qui eut son heure de gloire pendant le millénaire précédant notre ère, quand la ville de Luoyang, bâtie sur ses rives, était capitale de la Chine. Ses multiples versions parlent toutes d’une tortue portant d’étranges inscriptions sur son dos.

Une tortue légendaire

Pour calmer le dieu de la rivière, à chaque inondation, les habitants d’un village menacé d’être englouti lui offraient des sacrifices en vain. Cependant, ils remarquèrent qu’à chaque fois, une tortue venait sur les lieux du sacrifice et repartait. Le dieu du fleuve n’en tenait cure jusqu’à ce qu’un jour, un enfant remarqua des formes curieuses sur le dos de l’animal.

Dos de la tortue selon la légende

Dans chaque ligne, chaque colonne et chaque diagonale, le nombre était le même. Ainsi, les villageois comprirent que le dieu du fleuve demandait quinze sacrifices, et purent l’apaiser…

Les carrés magiques

Ce carré est depuis appelé « carré Luoshu » du nom de la rivière. Il a vite conquis le Moyen-Orient puis la Grèce où il était connu de Pythagore. Il est toujours utilisé comme amulette porte-bonheur et dans des exercices divinatoires. De nos jours, ces carrés où les sommes des nombres des lignes, colonnes et diagonales sont identiques sont appelés « carrés magiques », preuve de l’antique croyance. On peut de plus ajouter une contrainte, celle de n’utiliser que les premiers nombres donc ceux de 1 à 9, dans le cas d’un carré d’ordre trois, et ceux de 1 à 16 pour ceux d’ordre quatre. Avec cette dernière contrainte, il n’existe aucun carré d’ordre deux : vous pouvez disposer les nombres de 1 à 4 comme vous le voulez, le carré formé ne sera jamais magique. De ce fait, les pythagoriciens en faisaient un symbole du chaos. Aux symétries près, le carré d’ordre trois est unique, c’est le Luoshu (voir à la fin de cet article). De nos jours, les ésotériques préfèrent l’écrire de façon à faire apparaître le nombre 618 en première ligne car ce sont les premières décimales du nombre d’or. Pour eux, il devient ainsi doublement magique.

Le carré magique d’ordre 3

Carré magique d’ordre 3 faisant apparaître les décimales du nombre d’or.

Schéma de preuve

Si les cases du carré contiennent tous les nombres de 1 à 9, la somme de toutes les cases est 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9, c’est-à-dire 45. Les sommes de toutes les rangées et des diagonales sont donc égales à 45 divisé par 3, soit 15. Selon leur place, les nombres participent à 4, 3 ou 2 sommes égales à 15. En partant d’un nombre initial, comme 1, nous examinons le nombre de décompositions donnant 15 en tout. Pour 1, il en existe deux : 9 + 5 et 8 + 6. En opérant ainsi, nous obtenons le tableau :

Ce tableau permet de remplir le carré.

Les rubans de Pascal

Blaise Pascal (1623 – 1662) a inventé une méthode ingénieuse pour calculer le reste d’une division (sans l’effectuer) et donc de tester la divisibilité d’un nombre par un autre, que nous nommerons n dans la suite de cet article.

Une suite de restes

Pascal considère la suite des restes des puissances de 10 par n en commençant par 0, pour n = 7, cela donne :

puissances 0 1 2 3 4 5 6 7 8 9 10 11 12 13
restes 1 3 2 6 4 5 1 3 2 6 4 5 1 3

 

En effet, le reste de 1 est 1, celui de 10 est 3, celui de 100 est 2 (puisque 100 = 14 x 7 + 2), etc. La suite des restes est périodique. Ce résultat n’est pas lié au nombre 7, il est général. Cette suite est appelée le ruban de Pascal associé au nombre 7.

Calcul du reste d’une division

A partir de ce ruban, pour calculer le reste de la division par 7 d’un nombre comme 348, on écrit les décimales de 348 dans l’ordre inverse en dessous du début du ruban :

ruban 1 3 2
nombre 8 4 3
calculs 8 12=5 6 8+5+6=5

 

On effectue d’abord les multiplications en colonnes de 1 par 8, 3 par 4 et 2 par 3. On retranche autant de fois 7 que possible, donc 12 est remplacé par 5. On additionne alors les résultats obtenus et on retranche à nouveau autant de fois 7 que possible, on trouve 5 qui est le reste de la division de 348 par 7.

Pourquoi ? Cela vient des règles de calcul sur les nombres modulo 7 (c’est-à-dire en ne gardant à chaque étape que le reste dans la division par 7). On part de 348 = 3.102 + 4.101 + 8.100. En remplaçant, les puissances de 10 par leurs restes, on obtient 348 = 3.2 + 4.3 + 8.1 mod 7. On effectue les multiplications et les additions en retranchant 7 autant de fois qu’on peut et on a montré le bien fondé de l’algorithme utilisé ainsi que sa généralité.

On peut ainsi calculer très rapidement le reste des divisions de très grands nombres, comme celui de 56 218 491 par 7.

ruban 1 3 2 6 4 5 1 3
nombre 1 9 4 8 1 2 6 5
calculs 1 27=6 8=1 48=6 4 10=3 6 15=1 0

On trouve rapidement que le reste est égal à 0 donc que 56 218 491 est divisible par 7. Le test de divisibilité par 7 est donc de même nature que le test de divisibilité par 9 : au lieu de faire la somme des chiffres, on en fait une combinaison linéaire dont les coefficients sont ceux du ruban de Pascal. Il en est de même pour tous les nombres.

Divers rubans

Pour utiliser cette technique, il est bon de disposer d’un certain nombre de rubans. Voici ceux des nombres premiers inférieurs à 20 où on s’est arrêté à la partie périodique :

 

Nb
2 1 0
3 1 1
5 1 0
7 1 3 2 6 4 5 1
11 1 10 1
13 1 10 9 12 3 4 1
17 1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 1
19 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 1

 

On peut ainsi facilement déterminer le reste d’un nombre comme 521 365 941 dans la division par 19.

1 10 5 12 6 3 11 15 17
1 4 9 5 6 3 1 2 5
1 40=2 45=7 60=3 36=17 9 11 30=11 85=9 1+2+7+3+17+9+11+11+9=13

Le reste de 521 365 941 dans la division par 19 est donc 13.

 

Une carte à Léa

Une carte postale adressée à une jeune fille nommée Léa chez ses parents le 27 janvier 1905 a de quoi surprendre car elle ne comporte que des  nombres séparés de points ou de tirets.

Transcription de la carte

Le texte est constitué de nombres entre 2 et 25, qui représentent sans doute des lettres de l’alphabet, séparés par des points et des tirets. Les tirets séparent probablement les mots entre eux. Nous le reproduisons ici en remplaçant les tirets par des espaces :

25.22     21.2.8.8.24     7.22.4.19.2.20.20.24     25.2.23       5.24   12.9.24   17.24   18.22.23   24.5.4.23.18 17.24   20.22.14.22.23.8 4.23.24.20   4.24.5.9   19.24.7.9.23.8   2  17.2.9.4.8     17.22.23 23.9 18.24.8   2   5.22.4.18.24.8     5.24   25.22.18.23.20   17.24 20.22.23     4.23.24.20   24.9   22     17.22.14.24     8.23     18.9 8.22.14.22.23.8     5.2.25.25.24     17.24     8.9.23.8 23.25.7.22.18.23.24.20.18     12.9.22.20.19       24.13.13.24.8 8.2.20.18     24.20     4.24.18.22.4.19     22.9     4.24.14.2.23.4 25.2.20     22.20.21.24     22.19.2.4.24     18.2.9.18     22   18.2.23

Analyse

On remarque rapidement que le numéro 24 est majoritaire. Il représente sans doute le E. Un mot à l’avant dernière ligne se trouve alors à moitié décrypté. Il s’agit de 24.13.13.24.8. Le numéro 13 répété entre deux E ne peut être qu’une consonne, plus précisément L. On en déduit que ce mot est « elles ». Le suivant est alors probablement « sont ». Le chiffre s’écroule alors progressivement. En particulier la formule de politesse est « tout à toi ». Finalement, on obtient le texte :

Ma gosse, pardonne-moi ce que je t’ai écrit, je n’avais rien reçu depuis 2 jours. J’ai eu tes 2 cartes ce matin. Je n’ai rien eu à ja*e. Si tu savais comme je suis impatient quand elles sont en retard. Au revoir mon ange. Tout à toi.

L’étoile dans le texte est sans doute une erreur de chiffrement.

Les nombres premiers (définition)

A priori, les nombres premiers sont les nombres entiers naturels (1, 2, 3, 4 , 5, 6, etc.) qui ne sont divisibles que par 1 et eux-mêmes ce qui amène à éliminer dans la liste précédente les nombres composés c’est-à-dire produits de deux nombres comme 4 (2 x 2), 6 (2 x 3), etc.

1 est-il premier ?

Avec cette définition, 1 serait premier. On l’élimine pourtant en ajoutant qu’un nombre premier doit avoir deux diviseurs  distincts: 1 et lui-même. La raison est plus profonde qu’il ne peut paraître. Voyons pourquoi.

Le théorème fondamental de l’arithmétique

Si on exclut 1 de l’ensemble des nombres premiers, on peut démontrer un théorème fondamental en arithmétique :

tout nombre entier naturel supérieur à 2 est le produit d’un nombre fini de nombres premiers et ce de façon unique, à l’ordre près des facteurs.

Ainsi, 530 = 2 x 5 x 53

Pour démontrer ce théorème, l’essentiel est de montrer que tout nombre est soit premier, soit divisible par un nombre premier… ce qui est une évidence. En appliquant cette remarque de façon itérative, nous aboutissons à notre théorème.

Si on n’exclut pas 1, toute décomposition est multiple puisqu’on peut ajouter autant de facteurs 1 que l’on veut sans changer le résultat. Voila pourquoi on élimine 1 de la liste des nombres premiers.

 

 

Les pesées de Leibniz et de Bachet

Voici une question autrefois pratique, qui reste aujourd’hui ludique. Elle suppose l’utilisation d’une balance de Roberval, qui fut inventée par Gilles Personier de Roberval (1602 –  1675). Nous en donnons le schéma mais, pour comprendre l’usage que l’on en fait, il suffit de savoir que les deux plateaux s’équilibrent quand les masses qui s’y trouvent sont égales.

Schéma d’une balance de Roberval. Le parallélogramme articulé aux quatre sommets (en rouge) peut pivoter autour du point marqué (en blanc) sur la figure. L’aiguille est dirigée verticalement quand les poids sur les plateaux s’équilibrent.

Pesée binaire de Leibniz

Leibniz a montré que, si on dispose d’une série de poids dont chacun est le double du précédent, on peut réaliser toutes les pesées possibles. Pour voir comment, imaginons un objet de 713 grammes à peser avec des poids de 1, 2, 4, 8, 16, 32, 64, 128, 256 et 512 grammes. L’objet étant dans un plateau, nous commençons par placer le plus gros poids possible, c’est-à-dire celui de 512 grammes dans l’autre. Nous recommençons ensuite itérativement jusqu’à l’équilibre.

Voyons les étapes de ce processus. Le déficit est de 713 – 512 = 201 grammes. Nous utilisons alors le poids de 128 grammes (le plus gros possible). Il reste 201 – 128 = 73 grammes. Après le poids de 64 grammes, il ne reste plus que 9 grammes. Nous terminons en décomposant 9 en 8 + 1. Finalement, nous avons équilibré le poids de 713 grammes avec les poids prévus. D’un point de vue arithmétique, cela s’écrit :

713 = 512 + 128 + 64 + 8 + 1.

Ce résultat correspond à l’écriture de 713 en base deux : 713 = 29 + 27 + 26 + 23 + 20 ce que l’on peut noter : 1011001001. En base dix, nous écrivons : 713 = 7.102+ 101+ 3.100. La différence apparente est que l’écriture en base deux n’implique que des additions, pas de multiplication. En fait, il n’en est rien puisque les chiffres en base deux sont seulement 0 et 1 au lieu de 0, 1, …, 9. La propriété est générale, notre démarche prouve d’ailleurs que tout nombre s’écrit en binaire.

Pesée ternaire de Bachet

À l’occasion d’une récréation mathématique, Claude Bachet de Mériziac (1581 – 1638) a montré que, à condition d’utiliser les deux plateaux, on peut peser n’importe quel objet à l’aide d’une série de poids dont chacun est le triple du précédent. Voyons comment sur l’exemple précédent et des poids de 1, 3, 9, 27, 81, 243 et 729 grammes. L’idée précédente fonctionne si on dispose de deux poids de chaque sorte. Il suffit d’écrire 713 en ternaire. On commence par retrancher deux fois 243 à 713, il reste 227. On recommence avec deux fois 81, il reste 65. On retranche alors deux fois 27, il reste 11 ce qui fait 9 plus deux fois 1. Cette suite d’opérations fournit l’écriture ternaire : 222102 ce que l’on peut écrire : 713 = 2.35 + 2.34 + 2.33 + 32 + 2.30. Pour conclure, l’idée essentielle est d’éliminer les 2 du membre de droite de cette égalité en remarquant que : 3 = 2 + 1. Plus précisément : 713 + 35 + 34 + 33 + 30 = 36 + 35 + 34 + 32 + 31 ce qui se simplifie en : 713 + 33 + 30 = 36 + 32 + 31, c’est-à-dire en : 713 + 27 + 1 = 729 + 9 + 3. Il suffit donc de disposer des poids de 27 et 1 grammes dans le plateau de gauche et de 729, 9 et 3 grammes dans celui de droite.