Congruences
Calculer modulo n : compatibilité avec la somme, le produit et les puissances, inverse modulaire, critères de divisibilité, preuve par 9 et clé de Luhn.
- 25 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
a ≡ b (mod n) : de quoi s'agit-il ?
Voir la réponse
Les entiers a et b laissent le même reste dans la division par n ; de façon équivalente, n divise a − b.
38 ≡ 14 (mod 12), car 38 − 14 = 24 et 38 = 12 × 3 + 2, 14 = 12 × 1 + 2. Les entiers congrus modulo n se comportent à l'identique pour la somme et le produit.
Qu'affiche ce programme ?
```python
print((123456789 * 987654321) % 10)`9108
Voir la réponse
9Seul le dernier chiffre de chaque facteur compte modulo 10 : 9 × 1 = 9. Inutile de calculer le produit de dix-huit chiffres.
Si a ≡ b (mod n) et c ≡ d (mod n), alors a + c ≡ … et a × c ≡ … (mod n).
Voir la réponse
Si a ≡ b (mod n) et c ≡ d (mod n), alors a + c ≡ b + d et a × c ≡ b × d (mod n).
On peut donc réduire modulo n à chaque étape d'un calcul, sans manipuler de grand nombre : c'est ce qui rend les calculs de clés de contrôle, de hachage et de cycles possibles.
Classe de restes modulo n : de quoi s'agit-il ?
Voir la réponse
L'ensemble des entiers qui laissent un même reste r dans la division par n ; il y a exactement n classes, représentées par 0, 1, …, n − 1.
Modulo 5, la classe de 2 contient …, −8, −3, 2, 7, 12, … : calculer modulo n revient à calculer sur ces n classes.