Anneau Z/nZ et RSA en L2 de maths : exercices corrigés

---

---

Pour démarrer

Exercice 1 – Premiers calculs dans Z/14Z

Dans l’anneau \(\mathbb{Z}/14\mathbb{Z}\), donner le représentant compris entre \(0\) et \(13\) de chacune des classes suivantes.

1. \(\overline{9}+\overline{8}\), \(\overline{9}\times\overline{8}\) et l’opposé de \(\overline{5}\).
2. \(\overline{3}^{5}\), puis \(\overline{3}^{-1}\) après avoir justifié qu’il existe.
3. Montrer que \(\overline{4}\) n’est pas inversible en exhibant une classe non nulle \(\overline{y}\) telle que \(\overline{4}\,\overline{y}=\overline{0}\).

Exercice 2 – Lecture de la table de multiplication de Z/8Z

La figure donne la table de multiplication de \(\mathbb{Z}/8\mathbb{Z}\) : la case de la ligne \(a\) et de la colonne \(b\) contient le représentant de \(\overline{a}\,\overline{b}\).

1. À l’aide de la table, déterminer les classes inversibles et leurs inverses.
2. De même, repérer les diviseurs de zéro, c’est-à-dire les classes non nulles \(\overline{a}\) pour lesquelles il existe \(\overline{b}\neq\overline{0}\) avec \(\overline{a}\,\overline{b}=\overline{0}\).
3. Résoudre \(\overline{3}x=\overline{5}\), puis \(\overline{2}x=\overline{4}\), et enfin \(\overline{2}x=\overline{3}\).

Exercice 3 – Somme et intersection d’idéaux de Z

Cet exercice relie les idéaux de \(\mathbb{Z}\) au pgcd et au ppcm. En particulier, il demande des preuves par double inclusion.

1. Montrer que \(12\mathbb{Z}+18\mathbb{Z}=6\mathbb{Z}\).
2. Ensuite, trouver l’entier \(m\geq 0\) tel que \(12\mathbb{Z}\cap 18\mathbb{Z}=m\mathbb{Z}\).
3. L’ensemble \(2\mathbb{N}\) des entiers pairs positifs est-il un idéal de \(\mathbb{Z}\) ? Et l’ensemble \(2\mathbb{Z}\cup 3\mathbb{Z}\) ?

Exercice 4 – Inverse modulaire par Euclide étendu

On travaille ici avec le module \(74\). Ainsi, toutes les réponses seront données entre \(0\) et \(73\).

1. Justifier que \(\overline{31}\) est inversible dans \(\mathbb{Z}/74\mathbb{Z}\).
2. Calculer son inverse en remontant l’algorithme d’Euclide.
3. En déduire les solutions entières de \(31x\equiv 5\ [74]\).

Exercice 5 – Grandes puissances et petit théorème de Fermat

Aucun calcul de grande puissance n’est attendu. Au contraire, il faut réduire l’exposant avant de calculer.

1. Déterminer le reste de \(3^{100}\) dans la division par \(7\).
2. De même, trouver le reste de \(2^{2026}\) dans la division par \(13\).
3. Enfin, montrer que \(n^{13}-n\) est divisible par \(13\) pour tout entier \(n\).

Exercice 6 – Calculs d’indicatrice d’Euler

On rappelle que \(\varphi\) est multiplicative sur les entiers premiers entre eux. Par conséquent, une factorisation suffit pour la calculer.

1. Calculer \(\varphi(36)\), \(\varphi(97)\), \(\varphi(100)\) et \(\varphi(2026)\), sachant que \(1013\) est premier.
2. Ensuite, trouver tous les entiers \(n\geq 1\) tels que \(\varphi(n)=4\).

Exercice 7 – Dernier chiffre d’une puissance

Le dernier chiffre d’un entier positif est son reste modulo \(10\). Autrement dit, on calcule dans \(\mathbb{Z}/10\mathbb{Z}\).

1. Calculer \(\varphi(10)\) et en déduire le dernier chiffre de \(7^{2026}\) en écriture décimale.
2. Peut-on utiliser la même méthode pour le dernier chiffre de \(4^{2026}\) ? Déterminer ce chiffre.

Pour s’entraîner

Exercice 8 – Un système de trois congruences

Un collectionneur possède moins de \(315\) pièces. S’il forme des piles de \(5\), deux pièces restent à part. Avec des piles de \(7\), il lui en reste trois. Enfin, avec des piles de \(9\), quatre pièces sont isolées.

1. Traduire l’énoncé par un système de congruences et justifier qu’il admet une unique solution modulo \(315\).
2. Résoudre d’abord les deux premières congruences, puis ajouter la troisième.
3. Combien y a-t-il de pièces ?

Exercice 9 – Congruences à modules non premiers entre eux

Le théorème chinois ne s’applique pas directement dans cet exercice. Cependant, une substitution permet de conclure.

1. Résoudre le système \(x\equiv 3\ [8]\), \(x\equiv 7\ [12]\). On pourra écrire \(x=3+8k\).
2. Montrer que le système \(x\equiv 1\ [6]\), \(x\equiv 4\ [10]\) n’a aucune solution.
3. Énoncer une condition nécessaire, portant sur \(a-b\) et sur \(m\wedge n\), pour que le système \(x\equiv a\ [m]\), \(x\equiv b\ [n]\) soit compatible.

Exercice 10 – Équation linéaire dans Z/30Z

La classe de \(12\) n’est pas inversible modulo \(30\). C’est pourquoi on ne peut pas simplement diviser par \(12\).

1. Montrer que l’équation \(12x\equiv 18\ [30]\) équivaut à \(2x\equiv 3\ [5]\).
2. En déduire toutes ses solutions dans \(\{0,\dots,29\}\). Combien y en a-t-il ?
3. L’équation \(12x\equiv 20\ [30]\) a-t-elle des solutions ?

Exercice 11 – Inversibles et diviseurs de zéro

Soit \(n\geq 2\) et \(\overline{a}\neq\overline{0}\) dans \(\mathbb{Z}/n\mathbb{Z}\).

1. On suppose \(d=a\wedge n>1\). Montrer que \(\overline{a}\times\overline{n/d}=\overline{0}\) avec \(\overline{n/d}\neq\overline{0}\).
2. Établir ensuite qu’un élément inversible n’est jamais diviseur de zéro.
3. Conclure : les classes non nulles se partagent en deux familles disjointes, les inversibles et les diviseurs de zéro.

Exercice 12 – Équations du second degré modulo n

Les deux premières questions se placent dans le corps \(\mathbb{F}_{13}\). En revanche, la dernière se place dans un anneau qui n’est pas un corps.

1. Dans \(\mathbb{F}_{13}\), calculer l’inverse de \(\overline{2}\), puis vérifier que \(\overline{4}^2=\overline{3}\).
2. Résoudre dans \(\mathbb{F}_{13}\) l’équation \(x^2+3x+9=0\) en mettant le trinôme sous forme canonique.
3. Résoudre \(x^2=\overline{1}\) dans \(\mathbb{Z}/8\mathbb{Z}\). Expliquer pourquoi ce nombre de racines, supérieur au degré, reste compatible avec le cours.

Exercice 13 – Carrés modulo 11 et critère d’Euler

Le nombre \(11\) est premier, donc \(\mathbb{F}_{11}\) est un corps. Ainsi, tous les résultats du paragraphe sur les carrés s’appliquent.

1. Dresser la liste des carrés non nuls de \(\mathbb{F}_{11}\). Leur nombre est-il conforme au cours ?
2. Calculer \(5^5\) et \(7^5\) modulo \(11\), puis conclure à l’aide du critère d’Euler.
3. La classe \(-1\) est-elle un carré dans \(\mathbb{F}_{11}\) ? Relier la réponse au reste de \(11\) modulo \(4\).

Exercice 14 – Les idéaux de Z/12Z

On cherche à décrire tous les idéaux d’un anneau fini. Pour cela, on se ramène aux idéaux de \(\mathbb{Z}\), qui sont connus.

1. Soit \(I\) un idéal de \(\mathbb{Z}/12\mathbb{Z}\). Montrer que \(J=\{x\in\mathbb{Z}\ :\ \overline{x}\in I\}\) est un idéal de \(\mathbb{Z}\) contenant \(12\mathbb{Z}\).
2. En déduire que \(J=d\mathbb{Z}\) avec \(d\) diviseur de \(12\), puis que \(I\) est engendré par \(\overline{d}\).
3. Lister tous les idéaux de \(\mathbb{Z}/12\mathbb{Z}\) avec leur nombre d’éléments.

Exercice 15 – Le théorème chinois pour Z/15Z

Comme \(3\) et \(5\) sont premiers entre eux, \(\mathbb{Z}/15\mathbb{Z}\) s’identifie à \(\mathbb{Z}/3\mathbb{Z}\times\mathbb{Z}/5\mathbb{Z}\). Cet exercice exploite cette identification.

1. Trouver les entiers \(e_1\) et \(e_2\) de \(\{0,\dots,14\}\) tels que \(e_1\equiv 1\ [3]\), \(e_1\equiv 0\ [5]\), \(e_2\equiv 0\ [3]\) et \(e_2\equiv 1\ [5]\).
2. Vérifier que \(\overline{e_1}^2=\overline{e_1}\), \(\overline{e_2}^2=\overline{e_2}\) et \(\overline{e_1}\,\overline{e_2}=\overline{0}\) dans \(\mathbb{Z}/15\mathbb{Z}\).
3. Résoudre \(x\equiv 2\ [3]\), \(x\equiv 4\ [5]\) à l’aide de \(e_1\) et \(e_2\).
4. Enfin, trouver toutes les classes \(\overline{x}\) de \(\mathbb{Z}/15\mathbb{Z}\) telles que \(\overline{x}^2=\overline{x}\).

Exercice 16 – RSA avec de petits nombres

Bob choisit \(p=5\), \(q=11\) et l’exposant public \(e=3\).

1. Calculer \(n\) et \(\varphi(n)\), puis vérifier que \(e\) est admissible.
2. En déduire la clé privée \(d\).
3. Alice envoie le message \(m=8\). Calculer le message chiffré \(c\).
4. Déchiffrer \(c\) et vérifier que l’on retrouve \(m\).

Pour approfondir

Exercice 17 – Le théorème de Wilson

La figure relie chaque classe non nulle de \(\mathbb{F}_{13}\) à son inverse.

1. À l’aide de la figure, regrouper les facteurs du produit \(1\times 2\times\cdots\times 12\) et en déduire \(12!\) modulo \(13\).
2. Soit \(p\) un nombre premier. Montrer que les seules classes de \(\mathbb{F}_p\) égales à leur propre inverse sont \(\overline{1}\) et \(\overline{-1}\).
3. En déduire le théorème de Wilson : \((p-1)!\equiv -1\ [p]\).
4. Calculer \(16!\) et \(15!\) modulo \(17\).
5. Réciproquement, montrer que si \(n\geq 2\) n’est pas premier, alors \((n-1)!\not\equiv -1\ [n]\).

Exercice 18 – Quand -1 est-il un carré modulo p ?

Soit \(p\) un nombre premier impair.

1. À l’aide du critère d’Euler, montrer que \(-1\) est un carré de \(\mathbb{F}_p\) si et seulement si \(p\equiv 1\ [4]\).
2. Trouver un entier \(x\) tel que \(x^2\equiv -1\ [13]\), puis un entier \(y\) tel que \(y^2\equiv -1\ [17]\).
3. On suppose \(p\equiv 1\ [4]\). Montrer, à l’aide du théorème de Wilson, que \(x=\left(\frac{p-1}{2}\right)!\) vérifie \(x^2\equiv -1\ [p]\). On pourra écrire \(k\equiv -(p-k)\ [p]\).
4. Soit \(N\geq 2\) un entier. Montrer que tout facteur premier \(p\) de \(4(N!)^2+1\) vérifie \(p>N\) et \(p\equiv 1\ [4]\). En déduire qu’il existe une infinité de nombres premiers congrus à \(1\) modulo \(4\).

Exercice 19 – Problème – Un chiffrement RSA complet et son attaque

Bob choisit \(p=29\), \(q=41\) et \(e=3\).

1. Calculer \(n\) et \(\varphi(n)\). Vérifier que \(e\) est premier avec \(\varphi(n)\).
2. Déterminer la clé privée \(d\) comprise entre \(1\) et \(\varphi(n)\).
3. Alice veut transmettre \(m=100\). Calculer \(c\equiv m^3\ [n]\).
4. Déchiffrement accéléré. Réduire d’abord \(d\) modulo \(28\) et modulo \(40\), puis \(c\) modulo \(29\) et modulo \(41\). Ensuite, en déduire \(c^{d}\) modulo \(29\) et modulo \(41\). Enfin, retrouver \(m\) par le théorème chinois.
5. Expliquer pourquoi le calcul de \(c^d\) modulo \(29\) peut se faire avec l’exposant \(d\bmod 28\).
6. Un espion apprend que \(n=1189\) et \(\varphi(n)=1120\), sans connaître \(p\) et \(q\). Montrer qu’il peut retrouver \(p\) et \(q\) en résolvant une équation du second degré, et la résoudre.

Pour aller plus loin

Télécharger puis imprimer cette fiche en PDF.

Télécharger ou imprimer cette fiche «anneau Z/nZ et RSA en L2 de maths : exercices corrigés» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

 Maths PDF c'est 16 224 432 cours et exercices de maths téléchargés en PDF et 4 250 exercices.