Numérotons les lettres de l'alphabet de 0 pour A à 25 pour Z, et chiffrons un message en remplaçant chaque lettre de rang x par ax + b, calculé modulo 26. Le procédé s'appelle le chiffrement affine. Il est élémentaire, et il pose une question qui ne l'est pas : quels couples de coefficients produisent … Lire la suite de Chiffrer avec une fonction affine : tout se joue sur l’inverse modulaire
La chaîne du PGCD
Série en cours : de l’algorithme d’Euclide à l’identité de Bézout, au théorème de Gauss et aux nombres premiers.
Le crible d’Ératosthène : pourquoi peut-on s’arrêter à la racine carrée ?
Pour savoir si 211 est premier, personne ne teste 210 divisions. On s'arrête à 13, parce que 14² = 196 et 15² = 225 encadrent 211. La règle est enseignée partout ; sa justification, presque nulle part. Elle tient pourtant en trois lignes, et ces trois lignes disent quelque chose de plus général que le … Lire la suite de Le crible d’Ératosthène : pourquoi peut-on s’arrêter à la racine carrée ?
Le théorème de Gauss : quand a-t-on le droit de simplifier une divisibilité ?
Voici l'un des raisonnements faux les plus tenaces de l'arithmétique scolaire : puisqu'un entier divise un produit, il divise l'un des deux facteurs. La phrase sonne juste. Elle est fausse, et le contre-exemple tient en une ligne. 6 divise 4 × 9, mais 6 ne divise ni 4 ni 9. Le produit vaut 36, que … Lire la suite de Le théorème de Gauss : quand a-t-on le droit de simplifier une divisibilité ?
L’identité de Bézout, ou comment remonter l’algorithme d’Euclide
L'algorithme d'Euclide descend : il réduit un couple d'entiers jusqu'à leur PGCD. Ce que l'on ignore souvent, c'est qu'on peut le remonter, et qu'en le remontant on obtient bien davantage que le PGCD : on obtient une façon de l'écrire à partir des deux nombres de départ. C'est l'identité de Bézout, et elle ouvre la … Lire la suite de L’identité de Bézout, ou comment remonter l’algorithme d’Euclide
Exercice : trois nombres, un seul PGCD
L'algorithme d'Euclide donne le PGCD de deux entiers. Que devient-il lorsqu'on en a trois ? Et quel lien le PGCD entretient-il avec le PPCM ? L'exercice qui suit répond à ces deux questions, puis en pose une troisième dont la réponse surprend presque tous les élèves — et quelques enseignants. Le corrigé paraît dans l'article … Lire la suite de Exercice : trois nombres, un seul PGCD
L’algorithme d’Euclide : calculer un PGCD sans rien factoriser
Demandez à un élève de terminale le PGCD de 4 991 et de 1 219. Il cherchera les décompositions en facteurs premiers, parce que c'est la méthode qu'on lui a montrée, et il y passera un long moment : aucun des deux nombres ne se laisse factoriser de tête. Il existe pourtant un procédé qui donne la … Lire la suite de L’algorithme d’Euclide : calculer un PGCD sans rien factoriser
