Le calcul dans Z/nZ
Les classes modulo n, l'addition et la multiplication, les éléments inversibles et les diviseurs de zéro, l'inverse par l'algorithme d'Euclide étendu et la résolution de ax ≡ b modulo n.
- 26 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Z/nZ : de quoi s'agit-il ?
Voir la réponse
Ensemble des restes de la division par n, de 0 à n − 1, où l'on additionne et multiplie en gardant seulement le reste.
Dans Z/12Z, 9 + 5 vaut 2 : 14 a pour reste 2. Toute la cryptographie classique calcule dans un tel ensemble, avec n = 26 pour l'alphabet.
Lequel de ces éléments de Z/10Z n'a pas d'inverse ?
5379
Voir la réponse
5PGCD(5, 10) = 5, donc 5 n'est pas inversible, bien qu'il soit premier : 5 × 2 = 10 ≡ 0. Ce qui compte est le PGCD avec n, pas la primalité de l'élément. Les inversibles de Z/10Z sont 1, 3, 7 et 9.
Dans Z/nZ, un élément a est inversible si et seulement si ….
Voir la réponse
Dans Z/nZ, un élément a est inversible si et seulement si PGCD(a, n) = 1.
Si le PGCD est un d > 1, tout produit a × x est multiple de d, donc ne peut jamais valoir 1 modulo un n multiple de d.
Congruence modulo n : de quoi s'agit-il ?
Voir la réponse
Relation entre deux entiers qui ont le même reste dans la division par n, c'est-à-dire dont la différence est un multiple de n.
38 ≡ 12 (mod 26)car 38 − 12 = 26. Deux nombres congrus sont la même classe de Z/nZ : on peut les remplacer l'un par l'autre dans un calcul.