En mathématiques, et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l’étude du reste obtenu par une division euclidienne.
L'idée de base de l'arithmétique modulaire est de travailler non plus sur les nombres eux-mêmes, mais sur les restes de leur division par un nombre entier fixé (appelé le module). Par exemple, la méthode de la preuve par neuf utilisée à l'école primaire repose implicitement sur de l'arithmétique modulaire : le module est alors le nombre 9.
Ses origines remontent à l’Antiquité, aussi bien en Grèce antique, qu'en Chine et en Inde, ainsi qu'au Moyen-Âge, dans le monde musulman. Les historiens associent généralement sa naissance à l’année 1801, date de la publication des Disquisitiones arithmeticae. de Carl Friedrich Gauss. Son approche lui permet d’élucider plusieurs conjectures célèbresPar exemple la loi de réciprocité quadratique ou la construction à la règle et au compas de l’heptadécagone de . et de simplifier les démonstrations d’importants résultatsOn peut citer le théorème de Wilson ou le petit théorème de Fermat de . par une plus grande abstraction. Si le domaine naturel de ces méthodes est la théorie des nombres, les conséquences des idées de Gauss se retrouvent dans d’autres champs des mathématiques, comme l’algèbre ou la géométrie.
Le développement de l'informatique au modifie le statut de l’arithmétique modulaire. Un ordinateur, restreint physiquement par la taille de sa mémoire, ne peut pas travailler sur des entiers indéfiniment grands. L'arithmétique de base des ordinateurs travaille sur des nombres de taille limitée, les mots mémoire de taille fixe (8 bits, 16 bits, 32 bits, etc.), et est nécessairement une arithmétique modulaire. Le développement de nombreuses applications industrielles impose la mise au point d’algorithmes pour l'arithmétique modulaire. Ces algorithmes résolvent essentiellement des questions soulevées par le développement de l'informatique.
L’article « Congruence sur les entiers » propose une introduction plus mathématique ; « Anneau ℤ/nℤ » traite le même sujet de manière moins didactique et plus exhaustive.
Usages
En mathématiques pures, ce terme est très peu utilisé. La théorie algébrique des nombres désignant un domaine beaucoup plus large contenant par exemple les notions d'entiers algébriques. et de théorie de Galois Albert Fröhlich, Galois Module structure of Algebraic integers, Springer-Verlag, Berlin, 1983..
En mathématiques appliquées, cette expression est d'un usage fréquent pour décrire les bases mathématiques de différents domaines de la théorie de l'information : cryptologie, théorie des codes et informatique. De nombreux outils et algorithmes entrent dans ce champ d'étude. Parmi les tests de primalité les plus utilisésChantal David, Cryptographie à clé publique et factorisation, Université Concordia, ., l'utilisation des caractères d'un groupe par exemple pour la transformée de Fourier discrèteJ.-M. Muller et J.-C. Bajard, Calcul et arithmétique des ordinateurs, Traité Hermes CNRS 2004, et 181-201..
Selon les différents auteurs et le domaine d'application, ces extensions sont considérées, soit comme une partie intégrante de l'arithmétique modulaire, soit comme des applications, voire ne sont pas citées du tout. Sous sa forme simple, elle prend parfois le nom d'arithmétique de l'horloge..
Les systèmes modulaires de représentation (Residue number system, RNS en abrégé), des représentations des entiers fondée sur le théorème des restes chinois, sont utilisés pour accélérer les opérations de l'arithmétique modulaire..
Histoire Origines
Au , Euclide formalise, dans son livre les Éléments, les fondements de l'arithmétique. On y trouve notamment le lemme couramment nommé lemme d'Euclide, une version datée du théorème fondamental de l'arithmétique et une étude sur les nombres parfaits . dans la proposition 36 de son livre IXÉléments d'Euclide, Livre IX, Proposition 36.. Diophante d'Alexandrie (env. 250Les dates de naissance et de mort de Diophante sont mal connues, cf. Norbert Schappacher, Diophantus of Alexandria : a Text and its History, 2005.) écrit son Arithmetica qui contient 130 équations. Il traite essentiellement de problèmes ayant une unique solution numérique et à valeur fractionnaire ou entière. On y trouve que les nombres sommes de deux carrés parfaits ne sont jamais de la forme 4n + 3. Les équations, à coefficients entiers et dont les solutions recherchées sont entières, prennent aujourd'hui le nom d'équations diophantiennes.
La Chine développe parallèlement une arithmétique modulaire. Sun Zi écrit vers l'an 300 un traité de mathématiques dont le problème 26 du chapitre 3 est le suivant : Jean-Claude Martzloff, Histoire des mathématiques chinoises, Éditions Masson, 1988 , ..
Qin Jiushao (1202 - 1261) développe le théorème des restes chinoisQin Jiushao, Shushu Jiuzhang, (Traité mathématique en neuf sections), 1247.. Son traité est remarquablement avancé ; il traite d'un système de congruences linéaires dans le cas où les moduli ne sont pas premiers entre eux deux à deux. Ses travaux sur les systèmes de congruences dépassent en sophistication ceux de Leonhard Euler. On peut citer George Sarton pour qui :
Le voit un déclin progressif puis un oubli de ces résultats, le savoir de Qin Jiushao ne dépasse pas les frontières chinoises avant le . Il est redécouvert par les travaux de l'historien des sciences Joseph Needham. En revanche, de nombreuses similarités entre les notations arabes et chinoises laissent penser à des contacts durant les périodes précédentes..
L'Inde possède aussi une tradition forte en arithmétique. Aryabhata (476 - 550) recherche de manière systématique , « Aryabhata I », dans Hans Wussing et Wolfgang Arnold, Biographien bedeutender Mathematiker, Berlin, 1983. les solutions entières de l'équation linéaire à deux inconnues à coefficients entiers. Il utilise pour cela un algorithme appelé « Kuttaka » publié dans son livreAgathe Keller, Un commentaire indien du , thèse de l'université Paris-VII. appelé Âryabhatîya. Les équations diophantiennes de degré deux sont étudiées par Brahmagupta (598 - 668) S. S. Prakash Sarasvati, A critical study of Brahmagupta and his works, Delhi, 1986.. Au , Bhāskara II met au point la méthode chakravala.
La civilisation islamique joue un double rôle en arithmétique : elle véhicule le savoir acquis par les Grecs, Indiens, Chinois et Européens Shlomo Pinès, Studies in Arabic versions of Greek texts and in Medieval science, Leiden, 1986., et elle apporte des connaissances nouvellesRoshdi Rashed, Entre arithmétique et algèbre : Recherches sur l'histoire des mathématiques arabes, Les Belles Lettres, Paris, 1984 . notamment sur l'étude des propriétés de certains ensembles d'entiers, comme les nombres premiers, parfaits, amicaux ou figurésA. Djebbar, D. Savoie, D. Jacquart, M. El Faïz, L'Âge d'or des sciences arabes, exposition d'oct. 2005 à l'Institut du monde arabe, Actes Sud , .. Dans ce contexte, Qusta ibn Lûqâ réalise une traduction partielle de l'Arithmetica de Diophante d'Alexandrie à la fin du et Al-Hajjaj traduit à la même époque les Éléments d'Euclide John Lennart Berggren, Episodes in the Mathematics of Medieval Islam, Springer, 1986, . ; son collègue al-Khuwārizmī (env. 783 - env. 850) écrit un livre sur la numération indienne. Si le livre est perdu, il reste connu par une traduction latine Algoritmi de numero Indorum.. Thābit (836 - 901) étudie les nombres amicaux et les nombres parfaits Francis J. Carmody, Thabit b. Qurra, Four Astronomical Tracts in Latin, Berkeley, 1941.. Alhazen (965 - 1039) continue ses travaux sur les nombres parfaits et découvre le théorème de Wilson..
Apparition en Europe vignette|droite|Pierre de Fermat développe largement l'arithmétique. Les propriétés de la division euclidienne, fondement de l'arithmétique modulaire, sont largement utilisées par ce mathématicien. En 1621, Claude-Gaspard Bachet de Méziriac traduit le livre de Diophante en latin. Les questions soulevées intéressent les mathématiciens de l'époque. Pierre de Fermat propose un grand nombre d'énoncés, les trois plus célèbres étant probablement son grand théorème, son théorème des deux carrés et son petit théorème. La communauté scientifique se lance des défis sur ce sujet, ainsi Fermat demande : Il conclut par : Fermat, Correspondance, 3 janvier 1657.. Marin Mersenne recherche des nombres premiers particuliers. Fermat lui écrit : Fermat, Correspondance, lettre à Marin de Mersenne, 25 décembre 1640.. Ces nombres sont maintenant appelés nombres de Fermat et sa phrase s'avère être l'unique conjecture fausse proposée par l'auteur. René Descartes recherche sans y parvenir, à démontrer que si la division par huit d'un nombre premier donne pour reste un ou trois, il s'écrit de la forme x + 2y.
Sur ce type de problèmes, deux éléments sont remarquables : Les équations diophantiennes fascinent, le titre d'un des livres de Bachet de Méziriac est évocateur : Problèmes plaisants et délectables qui se font par les nombres, on peut citer encore la remarque de Fermat à propos de son grand théorème : <ref>Remarques de Fermat insérées par Pierre Samuel (son fils) dans l'édition de 1670 de lArithmetica de Diophante.</ref>
Les problèmes posés sont difficiles. Malgré quelques succès comme l'identité de Bézout probablement due à Bachet de Méziriac, l'essentiel des questions restent sans réponse, comme le théorème des deux carrés de Fermat, ou avec des réponses pour le moins peu convaincantes, comme celle de Fermat pour son grand théorème :«… mais la place me manque ici pour la développer » (la première preuve reconnue apparaîtra en 1995.). Bien souvent, Fermat termine ses théorèmes par des commentaires avouant son échec :
Méthodes utilisées vignette|droite|Leonhard Euler, théoricien des nombres du , résout plusieurs équations diophantiennes. Le siècle suivant voit la résolution de certaines de ces questions, souvent par Leonhard Euler : il contredit Fermat en démontrant que ses nombres ne sont pas toujours premiers, et prouve le théorème des deux carrésEuler, Correspondance, lettre à Goldbach, 12 avril 1749.. Il commet aussi des erreurs, sa tentative de démonstration du grand théorème de Fermat pour n égal à trois est un échec, sa première démonstration s'avère fausseEuler, Algèbre, 1770.. Il soulève d'autres questions comme la loi de réciprocité quadratique en 1782. Là encore, et malgré une tentative d'Adrien-Marie LegendreLegendre, Théorie des nombres, Paris, Duprat, 1798 ; Firmin Didot éd., 1830., la solution reste hors de portée.
Jusqu'à l'aube du les méthodes utilisées, si elles dénotent une grande astuce chez les mathématiciens, sont finalement peu nombreuses et de principes simples. L'exemple suivant, tiré du problème des deux carrés, en illustre trois : existe-t-il un nombre dont la division par quatre donne pour reste 3 et qui est somme de deux carrés ? Soit a et b ces deux carrés. Seul l'un est pair car sinon leur somme serait paire et sa division par 4 aurait 0 comme reste. Supposons a pair et b impair. a est pair donc son carré est un multiple de 4. L'entier b est impair donc s'écrit 2c + 1, son carré est égal à 4c + 4c + 1, la division de b par quatre donne pour reste un et la somme des deux carrés donne aussi pour reste un.
Le premier outil utilisé est celui des nombres premiers, ce raisonnement est exact car 2 est un nombre premier. Le deuxième est la transformation algébrique, b est transformé en 2c + 1. Utilisé avec virtuosité, il permet aux mathématiciens de l'époque de résoudre certaines équations diophantiennes. Toute l'astuce réside à choisir avec habileté les bonnes transformations. Le troisième est la division euclidienne, les carrés et leur somme sont systématiquement divisés par 4.