← Cours de mathématiques

Chapitre 11 — Structures algébriques

Maths Expertes · Math@mine · Exercices

⚠ HORS PROGRAMME BO Maths Expertes 2020. Exercices d'ouverture vers les classes préparatoires. Non exigibles au baccalauréat.
Ch10 📖 Cours ✏️ Exercices

I. Groupes — définition et premières propriétés

Exercice 1

Reconnaître un groupe

Pour chacune des structures suivantes, dire si c’est un groupe (commutatif ou non). Justifier en vérifiant les axiomes ou en exhibant un contre-exemple.

  1. \((\Z, -)\) où \(-\) est la soustraction.
  2. \((\R^*, \times)\) (réels non nuls avec la multiplication).
  3. \((\R_{>0}, \times)\) (réels strictement positifs).
  4. \((\mathcal{M}_2(\R), \times)\) (matrices \(2\times2\) avec le produit).
  5. \(\left(\{z \in \C \mid |z|=1\},\, \times\right)\) (nombres complexes de module 1).
  6. \((\Z/8\Z)^* = \{[1],[3],[5],[7]\}\) muni de la multiplication modulo 8.
Correction

a. Non : la soustraction n’est pas associative (\((5-3)-2=0\neq 5-(3-2)=4\)). L’élément neutre serait 0 (\(a-0=a\)) mais \(0-a\neq a\). Ce n’est pas un groupe.

b. Oui, groupe commutatif. Loi interne sur \(\R^*\) (produit de non-nuls est non-nul), associativité héritée de \(\R\), neutre 1, inverse \(1/x\). Commutatif car \(xy=yx\).

c. Oui, sous-groupe de \((\R^*,\times)\) : \(\R_{>0}\) est stable (produit de positifs > 0), neutre \(1\in\R_{>0}\), inverse \(1/x>0\).

d. Non : toutes les matrices \(2\times2\) ne sont pas inversibles (ex. la matrice nulle). Ce n’est pas un groupe. En revanche \(GL_2(\R)\) (matrices inversibles) en est un.

e. Oui, groupe commutatif. Si \(|z|=|w|=1\), alors \(|zw|=1\) (stable) ; associativité et commutativité héritées de \(\C^*\) ; neutre \(1\) ; inverse \(\bar{z}/|z|^2=\bar{z}\) et \(|\bar{z}|=1\).

f. Oui, groupe commutatif d’ordre 4. Table : \([1]\) neutre, \([3]^2=[9]=[1]\), \([5]^2=[25]=[1]\), \([7]^2=[49]=[1]\). Chaque élément est son propre inverse. Isomorphe à \(\Z/2\Z \times \Z/2\Z\).

Exercice 2

Table de Cayley et ordre des éléments

On considère le groupe \((\Z/6\Z, +)\).

  1. Dresser la table de Cayley (table d’addition modulo 6).
  2. Calculer l’ordre de chaque élément : \([0], [1], [2], [3], [4], [5]\).
  3. Quels éléments sont des générateurs du groupe ? Quel lien avec \(\pgcd(k, 6)\) ?
  4. Ce groupe est-il cyclique ? Citer un générateur.
Correction

a. Table d’addition modulo 6 :

+[0][1][2][3][4][5]
[0][0][1][2][3][4][5]
[1][1][2][3][4][5][0]
[2][2][3][4][5][0][1]
[3][3][4][5][0][1][2]
[4][4][5][0][1][2][3]
[5][5][0][1][2][3][4]

b. \(\text{ord}([0])=1\) ; \(\text{ord}([1])=6\) ; \(\text{ord}([2])=3\) (car \(3\times[2]=[0]\)) ; \(\text{ord}([3])=2\) ; \(\text{ord}([4])=3\) ; \(\text{ord}([5])=6\).

c. Les générateurs sont les éléments d’ordre 6 : \([1]\) et \([5]\). On a \(\pgcd(1,6)=1\) et \(\pgcd(5,6)=1\). Les non-générateurs vérifient \(\pgcd(k,6)>1\).

d. Oui, cyclique : \([1]\) est un générateur (\(\Z/6\Z = \langle [1] \rangle\)).

Exercice 3

Sous-groupes

On travaille dans \((\Z, +)\).

  1. Montrer que \(H = \{3k \mid k \in \Z\} = 3\Z\) est un sous-groupe de \((\Z,+)\).
  2. Montrer que \(K = \{5k \mid k \in \Z\} = 5\Z\) est un sous-groupe de \((\Z,+)\).
  3. Déterminer \(H \cap K\). Quel est ce sous-groupe de \(\Z\) ?
  4. Montrer que \(H \cup K\) n’est pas un sous-groupe de \(\Z\). (Indication : trouver deux éléments de \(H\cup K\) dont la somme n’y est pas.)
  5. D’après le théorème du cours, tout sous-groupe de \(\Z\) est de la forme \(n\Z\). Quel est le plus petit sous-groupe de \(\Z\) qui contient à la fois \(H\) et \(K\) ?
Correction

a. \(0=3\cdot0\in H\). Si \(a=3k, b=3l\in H\), alors \(a-b=3(k-l)\in H\). Critère du sous-groupe vérifié.

b. Même raisonnement avec 5.

c. \(H\cap K = \{n\in\Z \mid 3|n \text{ et } 5|n\} = \{n\mid 15|n\} = 15\Z\). (Car \(\pgcd(3,5)=1\), donc \(3|n\) et \(5|n\) implique \(15|n\).)

d. \(3\in H\subset H\cup K\) et \(5\in K\subset H\cup K\). Or \(3+5=8\), et \(8\notin 3\Z\) (car \(8=3\cdot2+2\)) et \(8\notin 5\Z\) (car \(8=5\cdot1+3\)). Donc \(8\notin H\cup K\). Pas stable par addition.

e. Le plus petit sous-groupe contenant \(H=3\Z\) et \(K=5\Z\) est le sous-groupe engendré par 3 et 5, soit \(\pgcd(3,5)\Z = 1\cdot\Z = \Z\). (Toute combinaison \(3u+5v\) génère \(\Z\) car \(\pgcd(3,5)=1\).)

II. ℤ/nℤ, groupes cycliques et ordre

Exercice 4

Ordre d’un élément et théorème de Lagrange

On considère le groupe \((\Z/12\Z, +)\) d’ordre 12.

  1. Calculer l’ordre de chaque élément \([k]\) pour \(k=0,1,\ldots,11\). (Rappel : \(\text{ord}([k]) = 12/\pgcd(k,12)\).)
  2. Vérifier que chaque ordre divise bien 12 (théorème de Lagrange).
  3. Lister tous les générateurs du groupe.
  4. Donner tous les sous-groupes de \(\Z/12\Z\). (Il y en a autant que de diviseurs de 12.)
Correction

a et b.

\(k\)01234567891011
\(\pgcd(k,12)\)1212341614321
\(\text{ord}([k])\)1126431221234612

Tous ces ordres (1, 2, 3, 4, 6, 12) divisent 12. ✓

c. Générateurs (ordre 12) : \([1],[5],[7],[11]\). Ce sont les \([k]\) avec \(\pgcd(k,12)=1\), soit \(\varphi(12)=4\) générateurs.

d. Les diviseurs de 12 sont 1, 2, 3, 4, 6, 12. Les sous-groupes correspondants :

  • Ordre 1 : \(\{[0]\}\)
  • Ordre 2 : \(\{[0],[6]\} = \langle[6]\rangle\)
  • Ordre 3 : \(\{[0],[4],[8]\} = \langle[4]\rangle\)
  • Ordre 4 : \(\{[0],[3],[6],[9]\} = \langle[3]\rangle\)
  • Ordre 6 : \(\{[0],[2],[4],[6],[8],[10]\} = \langle[2]\rangle\)
  • Ordre 12 : \(\Z/12\Z\) entier
Exercice 5

Groupe des inversibles \((\Z/n\Z)^*\)

On rappelle que \((\Z/n\Z)^* = \{[k] \mid \pgcd(k,n)=1\}\) est le groupe des éléments inversibles de l’anneau \(\Z/n\Z\), muni de la multiplication.

  1. Lister les éléments de \((\Z/10\Z)^*\) et calculer son ordre (indicatrice d’Euler \(\varphi(10)\)).
  2. Dresser la table de multiplication de \((\Z/10\Z)^*\).
  3. Calculer l’ordre de chaque élément. Ce groupe est-il cyclique ?
  4. Montrer que \([3]\) est un générateur de \((\Z/10\Z)^*\) en calculant ses puissances successives.
  5. Vérifier le petit théorème de Fermat : pour tout \(a\) avec \(\pgcd(a,10)=1\), montrer que \(a^{\varphi(10)} \equiv 1 \pmod{10}\).
Correction

a. \((\Z/10\Z)^* = \{[1],[3],[7],[9]\}\), ordre \(\varphi(10)=\varphi(2)\varphi(5)=1\times4=4\).

b. Multiplication modulo 10 :

×[1][3][7][9]
[1][1][3][7][9]
[3][3][9][1][7]
[7][7][1][9][3]
[9][9][7][3][1]

c. \(\text{ord}([1])=1\), \(\text{ord}([9])=2\) (\([9]^2=[81]=[1]\)), \(\text{ord}([3])=4\), \(\text{ord}([7])=4\). Comme il existe un élément d’ordre 4 = ordre du groupe, il est cyclique.

d. \([3]^1=[3]\), \([3]^2=[9]\), \([3]^3=[27]=[7]\), \([3]^4=[81]=[1]\). Toutes les classes sont atteintes. \([3]\) est bien un générateur.

e. Pour chaque \(a\in\{1,3,7,9\}\) : \(1^4=1\equiv1\), \(3^4=81\equiv1\), \(7^4=2401\equiv1\), \(9^4=6561\equiv1\pmod{10}\). ✓

III. Anneaux et corps

Exercice 6

Diviseurs de zéro et intégrité

Un anneau est dit intègre s’il n’a pas de diviseurs de zéro non nuls, i.e. \(ab=0 \Rightarrow a=0\) ou \(b=0\).

  1. Montrer que \(\Z\) est intègre.
  2. Montrer que \(\Z/6\Z\) n’est pas intègre en exhibant deux éléments non nuls dont le produit est nul.
  3. Montrer que \(\Z/7\Z\) est intègre. (Indication : utiliser que 7 est premier et le théorème de Gauss.)
  4. Soit \(A = \mathcal{M}_2(\R)\). Trouver deux matrices non nulles \(A, B\) telles que \(AB = 0\). Cet anneau est-il intègre ?
  5. Montrer que tout corps est intègre. (On rappelle que dans un corps, tout élément non nul est inversible.)
Correction

a. Si \(ab=0\) dans \(\Z\), c’est le produit de deux entiers nuls. Par définition de \(\Z\) (domaine d’intégrité), l’un des deux est nul.

b. \([2]\times[3]=[6]=[0]\) dans \(\Z/6\Z\), avec \([2]\neq[0]\) et \([3]\neq[0]\). Donc \(\Z/6\Z\) n’est pas intègre.

c. Supposons \([a][b]=[0]\) dans \(\Z/7\Z\), i.e. \(7\mid ab\). Comme 7 est premier, par Gauss : \(7\mid a\) ou \(7\mid b\), i.e. \([a]=[0]\) ou \([b]=[0]\). Intègre.

d. \(A=\begin{pmatrix}1&0\\0&0\end{pmatrix}\), \(B=\begin{pmatrix}0&0\\1&0\end{pmatrix}\). \(AB=\begin{pmatrix}0&0\\0&0\end{pmatrix}=0\). Non intègre.

e. Soit \(K\) un corps, \(ab=0\) avec \(a\neq0\). Alors \(a\) est inversible : \(a^{-1}\) existe. On multiplie : \(a^{-1}(ab)=(a^{-1}a)b=b=a^{-1}\cdot0=0\). Donc \(b=0\). Corps ⇒ intègre.

Exercice 7

\(\Z/p\Z\) est un corps

Soit \(p\) un nombre premier.

  1. Rappeler pourquoi \(\Z/p\Z\) est un anneau commutatif.
  2. Soit \([a]\neq[0]\) dans \(\Z/p\Z\). Montrer que \(\pgcd(a,p)=1\).
  3. En déduire l’existence de \(u,v\in\Z\) tels que \(au+pv=1\) (Bézout).
  4. Conclure que \([a]\) est inversible dans \(\Z/p\Z\), et que \(\Z/p\Z\) est un corps.
  5. Application : trouver l’inverse de \([3]\) dans \(\Z/7\Z\), puis de \([4]\) dans \(\Z/11\Z\).
Correction

a. \(\Z/p\Z\) hérite des lois de \(\Z\) : addition et multiplication sont internes (stables par réduction mod \(p\)), associatives, commutatives, distributives. Neutre pour + : \([0]\) ; pour × : \([1]\).

b. \([a]\neq[0]\) signifie \(p\nmid a\). Comme \(p\) est premier, ses seuls diviseurs sont 1 et \(p\). Donc \(\pgcd(a,p)=1\).

c. Par le théorème de Bézout : puisque \(\pgcd(a,p)=1\), il existe \(u,v\in\Z\) tels que \(au+pv=1\).

d. De \(au+pv=1\), on tire \(au\equiv1\pmod p\), i.e. \([a][u]=[1]\). Donc \([a]\) est inversible d’inverse \([u]\). Tout élément non nul étant inversible, \(\Z/p\Z\) est un corps.

e. \(\Z/7\Z\) : Euclide étendu \(7=2\cdot3+1\), donc \(1=7-2\cdot3\), soit \((-2)\cdot3\equiv1\pmod7\), donc \([3]^{-1}=[-2]=[5]\). Vérif : \(3\times5=15\equiv1\). ✓
\(\Z/11\Z\) : \(11=2\cdot4+3\), \(4=1\cdot3+1\), donc \(1=4-3=4-(11-2\cdot4)=3\cdot4-11\), so \([4]^{-1}=[3]\). Vérif : \(4\times3=12\equiv1\pmod{11}\). ✓

IV. Morphismes de groupes

Exercice 8

Vérifier qu’une application est un morphisme

Pour chacune des applications suivantes, vérifier s’il s’agit d’un morphisme de groupes (préciser les groupes de départ et d’arrivée), déterminer le noyau et l’image.

  1. \(f : (\Z,+) \to (\Z/3\Z, +)\) définie par \(f(n) = [n]\) (réduction modulo 3).
  2. \(g : (\R, +) \to (\R^*, \times)\) définie par \(g(x) = e^x\).
  3. \(h : (\Z,+) \to (\Z,+)\) définie par \(h(n) = 2n\).
  4. \(\varphi : (\Z/6\Z, +) \to (\Z/3\Z, +)\) définie par \(\varphi([n]) = [n]\) (réduction modulo 3 d’un représentant modulo 6).
Correction

a. \(f(m+n)=[m+n]=[m]+[n]=f(m)+f(n)\). ✓ Morphisme surjectif.
\(\ker f = \{n\mid [n]=[0]\} = 3\Z\). Image \(= \Z/3\Z\) (surjectif).

b. \(g(x+y)=e^{x+y}=e^xe^y=g(x)g(y)\). ✓ Morphisme de \((\R,+)\) dans \((\R^*,\times)\).
\(\ker g = \{x\mid e^x=1\} = \{0\}\) (injectif). Image \(= \R_{>0}^*\) (les exponentielles sont toujours > 0).

c. \(h(m+n)=2(m+n)=2m+2n=h(m)+h(n)\). ✓ Morphisme de \((\Z,+)\) dans \((\Z,+)\).
\(\ker h = \{0\}\) (injectif, car \(2n=0 \Rightarrow n=0\)). Image \(= 2\Z\) (entiers pairs). Non surjectif.

d. Bien définie : si \([n]=[n']\) dans \(\Z/6\Z\), alors \(6\mid n-n'\), donc \(3\mid n-n'\), donc \([n]=[n']\) dans \(\Z/3\Z\). ✓ Morphisme.
\(\varphi([n]+[m])=\varphi([n+m])=[n+m]=[n]+[m]=\varphi([n])+\varphi([m])\). ✓
\(\ker\varphi = \{[0],[3]\}\) (éléments congrus à 0 mod 3). Image \(= \Z/3\Z\) (surjectif).

Exercice 9 — Synthèse

Chiffrement RSA simplifié

Le chiffrement RSA repose sur les propriétés des groupes \((\Z/n\Z)^*\). On prend \(p=5, q=11\), donc \(n=pq=55\) et \(\varphi(n)=(p-1)(q-1)=40\).

  1. Rappeler pourquoi \((\Z/n\Z)^*\) est un groupe multiplicatif d’ordre \(\varphi(n)\).
  2. On choisit \(e=3\) comme clé publique (vérifier que \(\pgcd(3,40)=1\)). Trouver \(d\) tel que \(ed\equiv1\pmod{40}\) (clé privée). Indication : utiliser l’algorithme d’Euclide étendu.
  3. Pour chiffrer le message \(m=2\), calculer \(c=m^e\pmod{n}\) (cipher).
  4. Pour déchiffrer, calculer \(c^d\pmod{n}\) et vérifier qu’on retrouve \(m\).
  5. Pourquoi la relation \((m^e)^d \equiv m \pmod{n}\) est-elle garantie par le théorème de Lagrange (ou son corollaire) ?
Correction

a. \((\Z/n\Z)^*\) est l’ensemble des classes inversibles, stable par multiplication, et chaque élément est inversible par définition. Son ordre est \(\varphi(n)\) (nombre d’entiers entre 1 et \(n\) premiers avec \(n\)).

b. \(\pgcd(3,40)\) : \(40=13\times3+1\), donc \(\pgcd=1\). Bézout : \(1=40-13\times3\), donc \(3\times(-13)\equiv1\pmod{40}\), soit \(d\equiv-13\equiv27\pmod{40}\). Clé privée : \(d=27\).

c. \(c=2^3=8\pmod{55}\). Message chiffré : \(c=8\).

d. \(c^d=8^{27}\pmod{55}\). On calcule : \(8^2=64\equiv9\), \(8^4\equiv81\equiv26\), \(8^8\equiv676\equiv676-12\times55=676-660=16\), \(8^{16}\equiv256\equiv256-4\times55=256-220=36\), \(8^{27}=8^{16}\times8^8\times8^2\times8^1\equiv36\times16\times9\times8\pmod{55}\). Calcul : \(36\times16=576\equiv576-10\times55=26\) ; \(26\times9=234\equiv234-4\times55=14\) ; \(14\times8=112\equiv2\pmod{55}\). On retrouve \(m=2\). ✓

e. Par le corollaire de Lagrange (petit théorème de Fermat généralisé) : pour tout \(m\) avec \(\pgcd(m,n)=1\), \(m^{\varphi(n)}\equiv1\pmod n\). Or \(ed=1+k\varphi(n)\), donc \(m^{ed}=m\cdot(m^{\varphi(n)})^k\equiv m\cdot1^k=m\pmod n\).

Maths Expertes — Math@mine · Ch11 Structures algébriques