La définition des ces deux opérations est somme toute simple: deux nombres $a$ et $b$ sont égaux (ou équivalents) modulo $n$ si leur différence est un multiple de $n$, ou, formulée d'une autre manière, si $b$ est le reste de la division de $a$ sur $n$. $$a \equiv b [n] \iff a = n . k + b \text{ (pour un certain } k \in \mathbb{Z} \text{)}$$ Par exemple:
$3 \equiv 13 [10]$
$5 \equiv 33 [14]$
$-1 \equiv 13 [14]$
etc...
Il y a une relation très étroite entre cette définition du calcul modulo (c'est ce qu'on appelle l'arithmétique modulaire) et ce qu'on a vu la dernière fois concernant les groupes quotients $\mathbb{Z}/n\mathbb{Z}$, car, regardez bien:
- On a dit que deux nombres (de $\mathbb{Z}$) sont égaux ou équivalents modulo $n$ si leur différence $a-b$ est un multiple de $n$ (donc si la différence appartient à $n\mathbb{Z}$), c'est à dire si $a \star b^{-1} \in \mathbb{Z}$ (avec $\star \doteq +$ et $b^{-1} \doteq -b$, $\doteq$ voulant dire est définie par...), cette dernière définition on la connait! Elle veut dire que $a$ et $b$ appartiennent à la même classe d'équivalence du groupe quotient $\mathbb{Z}/n\mathbb{Z}$ [se rafraîchir la mémoire avec le résumé de la séance].
Donc, faire de l'arithmétique (du calcul) modulaire revient à faire des opérations entre des classes d'équivalence du groupe quotient $\mathbb{Z}/n\mathbb{Z}$, par exemple si on dit que $3 \equiv 14 [11]$ cela veut dire que $3$ et $14$ appartiennent à la même classe d'équivalence du groupe quotient $\mathbb{Z}/11\mathbb{Z}$, cette classe d'équivalence qu'on peut représenter par le plus petit élément $\dot{3}$ et qui vaut $\dot{3} = \{\dots, -19, -8, 3, 14, 25, \dots\}$, c'est parce que les deux éléments $3$ et $14$ appartiennent à une même classe d'équivalence de $\mathbb{Z}/11\mathbb{Z}$ qu'on dit qu'ils sont égaux ou équivalents modulo 11, et le groupe quotient est l'ensemble des classes d'équivalence $\mathbb{Z}/11\mathbb{Z} = \{\dot{0},\dot{1},\dot{2},\dot{3},\dot{4},\dot{5},\dot{6},\dot{7},\dot{8},\dot{9},\dot{10}\}$
- Quand vous voulez vous connecter à un site (se trouvant dans un serveur) pour consulter par exemple votre boîte email, la connexion établie doit être cryptée pour qu'aucune personne ayant le contrôle d'un des ordinateurs qui permettent de faire le relais entre votre PC et le serveur ne soit en mesure de décrypter et lire les données, une des méthodes de cryptage possibles (et très sûre) est ce qu'on appelle le chiffrement RSA [voilà deux liens 1 et 2 pour lire de quoi il s'agit] qui est basé sur l’arithmétique modulaire, vous pouvez voir qu'on y utilise $mod$ pour dire modulo (c'est la même chose que notre $[...]$), vous pouvez voir aussi que vous êtes en ce moment même surement entrain d'utiliser une connexion cryptée RSA qui utilise le calcul modulaire dont on parle ici (ouvrez votre boîte email, vous verrez que l'adresse internet, l'URL, ne commence plus par http:// mais https://, le "s" veut dire "sécurisée", si vous cliquez sur l'icone à coté, et que vous lisez bien, vous trouverez à coup sur le mot RSA)
Pour pouvoir décrypter ou cracker ce genre de clés, il est donc primordiale d'avoir de bonnes connaissances en mathématiques, en particulier en calcul combinatoire, en arithmétique modulaire (ce qu'on fait ici) et même en théorie de groupes (ce qu'on fait dans ce semestre), mais je vous rassure, les clés RSA que vous utilisez sont très sûres (enfin... officiellement...)
- Exercice 1 l'ensemble $E = \{0,2,4,6,8\}$ est muni de deux lois $\dot+$ et $\dot\times$ définies comme suit:
$\forall (a,b) \in E^{2} : a \dot+ b = c \text{ }$ où $c$ est le chiffre des unités de $a+b$
$\forall (a,b) \in E^{2} : a \dot\times b = d \text{ }$ où $d$ est le chiffre des unités de $a\times b$
- Construire les tables des opérations $\dot+$ et $\dot\times$
- Montrer que $(E,\dot+,\dot\times)$ possède une structure d'anneau commutatif unitaire et que tout élément de $E$ autre que $0$ est symétrisable
- Calculer le nombre: $$x = \frac{4 \dot\times (4 \dot+ 8)^{2} \dot+ 8}{(2\dot+ 4)^{3} \dot+ 2}$$
- Construire les tables des opérations $\dot+$ et $\dot\times$
- Corrigé 1 Avant de répondre aux questions remarquons que les deux lois $\dot+$ et $\dot\times$ peuvent être définies en utilisant l'arithmétique modulaire, en effet: $$\forall (a,b) \in E : \, a \dot+ b \equiv (a + b) [10]$$ $$\forall (a,b) \in E : \, a \dot\times b \equiv (a \times b) [10]$$ On aura besoin aussi d'une autre relation, démontrons la avant de commencer:
On remarque tout d'abord que si $a \in E$ on peut écrire l'égalité $a = a [10]$
Maintenant, on sait que $\forall (a,b) \in E^{2}:\; a \dot+ b \in E$ car $\dot+$ est une l.c.i, donc on peut écrire: $$(a \dot+ b) = (a \dot+ b) [10]$$ Et on utilisant la définition de $a \dot+ b$ on trouve: $$(a \dot+ b) [10] \equiv (a + b) [10]$$ Cette relation veut dire que quand on travaille à l’intérieure d'une classe d'équivalence $[10]$, on peut remplacer $a \dot+ b$ par $a + b$, cela va nous être utile par la suite.
- Tables des opérations $\dot+$ et $\dot\times$
$\dot+$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $2$ $4$ $6$ $8$ $2$ $2$ $4$ $6$ $8$ $0$ $4$ $4$ $6$ $8$ $0$ $2$ $6$ $6$ $8$ $0$ $2$ $4$ $8$ $8$ $0$ $2$ $4$ $6$ $\dot\times$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $0$ $0$ $0$ $0$ $2$ $0$ $4$ $8$ $2$ $6$ $4$ $0$ $8$ $6$ $4$ $2$ $6$ $0$ $2$ $4$ $6$ $8$ $8$ $0$ $6$ $2$ $8$ $4$ - Pour que $(E,\dot+,\dot\times)$ soit un anneau commutatif unitaire on doit avoir:
- pour que $(E,\dot+,\dot\times)$ soit un anneau
- $(E,\dot+)$ doit être un groupe abélien c'est à dire:
- $\dot+$ doit être une l.c.i dans $E$
- $\dot+$ doit être commutative
- $\dot+$ doit admettre un élément neutre
- chaque élément de $E$ doit être symétrisable par rapport à $\dot+$
- $\dot+$ doit être associative
- $\dot+$ doit être une l.c.i dans $E$
- $\dot\times$ doit être associative et distributive par rapport à $\dot+$ dans $E$
- $(E,\dot+)$ doit être un groupe abélien c'est à dire:
- pour qu'il soit commutatif
- $\dot\times$ doit être commutative dans $E$
- pour qu'il soit unitaire
- $\dot\times$ doit admettre un élément neutre dans $E$
- $\dot+$ est-elle une l.c.i? Oui, on peut le voir à partir de la table des opérations de $\dot+$: toutes les cases sont remplies par des éléments de $E$.
- $\dot+$ est-elle commutative? Oui, on peut le voir aussi à partir de la table des opérations de $\dot+$, elle est symétrique par rapport à la diagonale (par exemple $4 \dot+ 2 = 2 \dot+ 4$, ...etc)
$\dot+$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $2$ $4$ $6$ $8$ $2$ $2$ $4$ $6$ $8$ $0$ $4$ $4$ $6$ $8$ $0$ $2$ $6$ $6$ $8$ $0$ $2$ $4$ $8$ $8$ $0$ $2$ $4$ $6$ - $\dot+$ admet-elle un élément neutre? Oui, et c'est $e=0$, on le voit à partir de la tables des opérations de $\dot+$, la ligne $0,2,4,6,8$ ne change pas pour l'élément $0$
$\dot+$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $2$ $4$ $6$ $8$ $2$ $2$ $4$ $6$ $8$ $0$ $4$ $4$ $6$ $8$ $0$ $2$ $6$ $6$ $8$ $0$ $2$ $4$ $8$ $8$ $0$ $2$ $4$ $6$ - chaque élément est-il symétrisable? Oui, car pour chaque colonne (ou ligne) on peut trouver une case remplie avec l'élément neutre $0$ dans la table des opérations de $\dot+$, plus précisément on a: $0^{-1} = 0,\,2^{-1}=8,\,4^{-1}=6,\text{...etc}$
$\dot+$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $2$ $4$ $6$ $8$ $2$ $2$ $4$ $6$ $8$ $0$ $4$ $4$ $6$ $8$ $0$ $2$ $6$ $6$ $8$ $0$ $2$ $4$ $8$ $8$ $0$ $2$ $4$ $6$ - $\dot+$ est-elle associative? Oui, car: $$\begin{eqnarray*} \forall(a,b,c)\in E^{3}:\,(a\dot{+}b)\dot{+}c & \equiv & \left((a\dot{+}b)+c\right)[10]\\ & \equiv & \left((a+b)+c\right)[10]\\ & \equiv & \left(a+(b+c)\right)[10]\\ & \equiv & \left(a+(b\dot{+}c)\right)[10]\\ & \equiv & a\dot{+}(b\dot{+}c)\end{eqnarray*}$$ Mais comme $$\forall(a,b,c)\in E^{3}:\,(a\dot{+}b)\dot{+}c\in E\;\wedge a\dot{+}(b\dot{+}c)\in E$$ L'équivalence $\equiv$ est en fait une égalité $=$, on a donc: $$\forall(a,b,c)\in E^{3}:\,(a\dot{+}b)\dot{+}c=a\dot{+}(b\dot{+}c)$$
- $\dot\times$ est-elle associative? Oui, car: $$\begin{eqnarray*} \forall(a,b,c)\in E^{3}:\,(a\dot{\times}b)\dot{\times}c & \equiv & \left((a\dot{\times}b)\times c\right)[10]\\ & \equiv & \left((a\times b)\times c\right)[10]\\ & \equiv & \left(a\times(b\times c)\right)[10]\\ & \equiv & \left(a\times(b\dot{\times}c)\right)[10]\\ & \equiv & a\dot{\times}(b\dot{\times}c)\end{eqnarray*}$$ Mais comme $$\forall(a,b,c)\in E^{3}:\,(a\dot{\times}b)\dot{\times}c\in E\;\wedge a\dot{\times}(b\dot{\times}c)\in E$$ L'équivalence $\equiv$ est en fait une égalité $=$, on a donc: $$\forall(a,b,c)\in E^{3}:\,(a\dot{\times}b)\dot{\times}c=a\dot{\times}(b\dot{\times}c)$$
- $\dot\times$ est-elle distributive par rapport à $\dot+$? Oui, car: $$\begin{eqnarray*} \forall(a,b,c)\in E^{3}:\,(a\dot{+}b)\dot{\times}c & \equiv & \left((a\dot{+}b)\times c\right)[10]\\ & \equiv & \left((a+b)\times c\right)[10]\\ & \equiv & \left((a\times c)+(b\times c)\right)[10]\\ & \equiv & \left((a\dot{\times}c)+(b\dot{\times}c)\right)[10]\\ & \equiv & (a\dot{\times}c)\dot{+}(b\dot{\times}c)\end{eqnarray*}$$ Mais comme: $$\forall(a,b,c)\in E^{3}:\,(a\dot{+}b)\dot{\times}c\in E\;\wedge(a\dot{\times}c)\dot{+}(b\dot{\times}c)\in E$$ L'équivalence $\equiv$ est en fait une égalité $=$, on a donc: $$\forall(a,b,c)\in E^{3}:\,(a\dot{+}b)\dot{\times}c=(a\dot{\times}c)\dot{+}(b\dot{\times}c)$$
- $\dot\times$ est-elle commutative? Oui, on peut le voir à partir de la table des opérations de $\dot\times$, elle est symétrique par rapport à la diagonale (par exemple $4 \dot\times 2 = 2 \dot\times 4$, ...etc)
$\dot\times$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $0$ $0$ $0$ $0$ $2$ $0$ $4$ $8$ $2$ $6$ $4$ $0$ $8$ $6$ $4$ $2$ $6$ $0$ $2$ $4$ $6$ $8$ $8$ $0$ $6$ $2$ $8$ $4$ - $\dot\times$ admet-elle un élément neutre? Oui, car dans chaque colonne (ou ligne) d'un élément (autre que l'élément neutre de $\dot+$ qui est le $0$) on peut trouver une case telle que la ligne (ou colonne) correspondante est celle du même élément. L'élément neutre est $6$ et il est facile de le vérifier: $2 \dot\times 6 = 2,\,4 \dot\times 6 = 4,\,\text{...etc}$
$\dot\times$ $0$ $2$ $4$ $6$ $8$ $0$ $0$ $0$ $0$ $0$ $0$ $2$ $0$ $4$ $8$ $2$ $6$ $4$ $0$ $8$ $6$ $4$ $2$ $6$ $0$ $2$ $4$ $6$ $8$ $8$ $0$ $6$ $2$ $8$ $4$
- pour que $(E,\dot+,\dot\times)$ soit un anneau
- Calcul du nombre $x$ $$\begin{eqnarray*} x & = & \frac{4\dot{\times}(4\dot{+}8)^{2}\dot{+}8}{(2\dot{+}4)^{3}\dot{+}2}\\ & = & \frac{4\dot{\times}(2)^{2}\dot{+}8}{(6)^{3}\dot{+}2}\\ & = & \frac{4\dot{\times}2\dot{\times}2\dot{+}8}{6\dot{\times}6\dot{\times}6\dot{+}2}\\ & = & \frac{8\dot{\times}2\dot{+}8}{6\dot{+}2}\text{ (car 6 est element neutre par rapport a }\dot{\times}\text{)}\\ & = & \frac{6\dot{+}8}{6\dot{+}2}\\ & = & \frac{4}{8}\text{ (ici la division represente l'operation inverse de }\dot{\times}\text{)}\\ & = & 4\dot{\times}8^{-1}\\ & = & 4\dot{\times}2\text{ (car dans la table des operations de }\dot{\times}\text{ on a }8\dot{\times}2=6=e\text{)}\\ & = & 8\end{eqnarray*}$$
- Tables des opérations $\dot+$ et $\dot\times$
Aucun commentaire:
Enregistrer un commentaire