Congruences et arithmétique modulaire

L'arithmétique modulaire étudie les entiers jusqu'à la divisibilité par un module fixe, transformant les entiers en l'anneau fini Z/nZ et offrant à la théorie des nombres son outil de calcul le plus flexible.

Definition

Deux entiers sont congrus modulo n si leur différence est divisible par n. L'arithmétique modulaire est l'arithmétique des classes de résidus résultantes, qui forment l'anneau commutatif Z/nZ.

Scope

Ce sujet couvre la relation de congruence et les classes de résidus, l'arithmétique dans Z/nZ, les congruences linéaires et polynomiales, le théorème des restes chinois, le petit théorème de Fermat et le théorème d'Euler, la structure du groupe des unités, les racines primitives et l'ordre des éléments. C'est le langage dans lequel la majeure partie de la théorie des nombres élémentaire et computationnelle est exprimée.

Core questions

• Quand une congruence linéaire ax congru à b mod n a-t-elle des solutions, et combien ?
• Comment le théorème des restes chinois décompose-t-il Z/nZ en un produit sur des modules de puissance première ?
• Pourquoi le petit théorème de Fermat et le théorème d'Euler sont-ils valides, et que disent-ils sur l'ordre des unités ?
• Pour quels modules une racine primitive existe-t-elle, rendant le groupe des unités cyclique ?

Key theories

Théorème des restes chinois

Si les modules sont premiers entre eux deux à deux, un système de congruences simultanées a une solution unique modulo le produit ; de manière équivalente, Z/nZ est isomorphe au produit de Z sur ses facteurs de puissance première.

Petit théorème de Fermat et théorème d'Euler

Pour a premier avec n, a élevé à l'indicatrice d'Euler de n est congru à un modulo n ; le cas premier (Fermat) sous-tend les tests de primalité et le cas général sous-tend RSA.

Racines primitives et structure de groupe

Le groupe multiplicatif des unités modulo n est cyclique exactement lorsque n est un, deux, quatre, une puissance de nombre premier impair, ou le double de un ; un générateur est une racine primitive, donnant un logarithme discret.

Clinical relevance

L'arithmétique modulaire est le moteur computationnel de la cryptographie (RSA, Diffie-Hellman, schémas à courbe elliptique), des sommes de contrôle et de la détection d'erreurs (ISBN, fonctions de hachage), et de la génération de nombres pseudo-aléatoires, ce qui en fait la partie la plus largement déployée de la théorie des nombres.

History

Bien que des cas particuliers apparaissent dans les mathématiques chinoises et indiennes anciennes (le problème des restes nommé d'après les premières), la théorie systématique des congruences a été introduite par Gauss dans les Disquisitiones Arithmeticae (1801), où il a établi la notation et prouvé les résultats structurels centraux.

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

Que signifie la notation a congru à b mod n ?

Cela signifie que n divise la différence a moins b, ou de manière équivalente, que a et b laissent le même reste lors de la division par n.

Pourquoi RSA repose-t-il sur le théorème d'Euler ?

Le chiffrement et le déchiffrement RSA sont des exponentiations modulaires dont la composition renvoie le message original précisément parce que le théorème d'Euler garantit que l'exposant pertinent agit comme l'identité modulo la clé.