Calcul modulaire Z/nZ
Voici les nombres de 1 à n (ou de -n/2 à +n/2). On peut les ajouter, les multiplier, regarder leurs multiples, et prendre le reste dans la division euclidienne par n. Ce n'est pas banal que les opérations habituelles sur les nombres fonctionnent encore quand on ne retient que leur reste modulo n!
Observez bien la différence qu'il y a entre n premier (sans diviseur autre que 1 et lui-même) et n composé. Dans le premier cas, chaque nombre non nul génère tous les autres et a un inverse. Si n=p×q par contre, p est un diviseur de zéro de q, leur produit est nul!
Faites apparaître les multiples de A et notez qu'ils sont un sous-ensemble des entiers. Il faut que A soit premier avec n pour posséder un inverse et être générateur.
L'ensemble des entiers modulo n peut-être vu sous la forme des racines n-ème de l'unité du cercle trigonométrique . Sous forme exponentielle, on les note car est -périodique: pour tout entier k, .
Un entier est générateur des autres quand il est premier avec n. Cet ensemble des générateurs (visible quand on affiche les multiples de A) est dénombré par , l'indicatrice d'Euler. Remarquez bien la grande différence des multiples de A quand le point de départ est générateur ou qu'il ne l'est pas! S'il n'est pas générateur, ses multiples forment un sous-groupe de . Étudions cela plus avant avec les racines primitives.