cours précédents :
ensembles (Cours du 27 septembre 2018)
Arithmétique modulaire :
ℤp est un corps (chaque élément a un inverse pour la multiplication)
ce sont les tables d'addition et de multiplication qui donne les résultats des opérations.
classe d'équivalence de a modulo n : a = { a + k n avec k∈ℤ }
on prend le représentant a tel que a ∈ [ 0 ; n−1 ]
Calculer Identité de Bézout : PGCD
Exemple ℤ5 : nombres [0, 1, 2, 3, 4]
table d'addition
table de multiplication
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
+
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
Résoudre : 3 x + 4 = 0 recherche de l'opposé de 4 dans la table(+) : 4+1=0
3x+4+1=0+1
3x=1
recherche de l'inverse de 3 dans la table(+) : 3×2=1
x = 2
la connaissance des opposés et des inverses suffit pour faire les calculs.
1+4=0 ; 2+3=0 (0+0=0 sans intérêt)
2×3=1 ; 4×4=1 (0×n=0 ; 1×1=1 sans intérêt)
équation sans solution : 0 x = 1
équation toujours vraie : 0 x = 0 ∀x ∈ ℤ/5
ℤn Opposé de a (pour l'addition) : complément à n opposé(a) = n−a ; en effet : a + (n−a) = n ≡ 0 (mod n)
Inverse de a≠0 (pour la multiplication) : Identité de Bézout : u a + v n = 1 ⇒ ua + vn = 1 Or n = 0 : donc ua = 1 l'inverse de a est u, son coefficient u dans l'identité de Bézout(a,n) si a et n ne sont pas premiers entre eux, a ne possède pas d'inverse et est un diviseur de 0.
Attention : ℤ6 possède des diviseurs de 0 : 2×3=0
table de multiplication
+
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
0
2
4
3
0
3
0
3
0
3
4
0
4
2
0
4
2
5
0
5
4
3
2
1
On voit que 3x=2 n'a pas de solution,
alors que 3x=3 a 3 solutions