BURHAN.

Ensemble ℤ/nℤ : Cours de Mathématiques 2BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ

Ensemble ℤ/nℤ : notion du chapitre Arithmétique dans ℤ du programme de maths 2BAC SM, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).

Notions du cours (11)

Apprendre avec Burhan

L'ensemble ℤ/nℤ

Étape 1 sur 5

Ranger les entiers par restes

Devine : Les jours de la semaine

Aujourd'hui est un mercredi. Quel jour de la semaine serons-nous dans 100100 jours ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Mercredi

Faux.

Ce serait vrai si 100100 était un multiple de 77. Or 7×14=987 \times 14 = 98 : il reste 22 jours.

Choix B :Vendredi

Juste.

100=7×14+2100 = 7 \times 14 + 2 : quatorze semaines entières, puis 22 jours après mercredi.

Choix C :Jeudi

Faux.

Tu as compté un seul jour de reste. Or 100−98=2100 - 98 = 2 : il en reste deux.

Besoin d'aide ? Indice 1

Le calendrier revient au même jour toutes les 77 journées.

Encore bloqué ? Indice 2

Cherche le reste de 100100 dans la division par 77.

Voir la correction complète

100=7×14+2100 = 7 \times 14 + 2, avec 0≤2<70 \leq 2 < 7 : dans 100100 jours, on sera 22 jours après mercredi, un vendredi. Le calendrier ne distingue pas 22, 99, 1616 ou 100100 jours, qui ont le même reste modulo 77. Regrouper ces entiers, c'est former une classe.

DéfinitionClasses modulo n et ensemble ℤ/nℤ

Soit nn un entier naturel, n≥2n \geq 2. Pour tout entier relatif aa, la classe de aa modulo nn est l'ensemble des entiers relatifs congrus à aa modulo nn : a‾={ b∈Z / b≡a [n] }.\overline{a} = \{\, b \in \mathbb{Z} \ / \ b \equiv a \ [n] \,\}. L'ensemble des classes modulo nn se note Z/nZ\mathbb{Z}/n\mathbb{Z}.

ExempleLes classes modulo 5

Modulo 55, il y a cinq restes possibles, donc cinq tiroirs. Par exemple :

3‾={…,−7,−2,3,8,13,… }.\overline{3} = \{\dots, -7, -2, 3, 8, 13, \dots\}.

Ainsi 3‾=8‾=−2‾\overline{3} = \overline{8} = \overline{-2} : n'importe quel élément peut nommer la classe. Pourquoi y a-t-il exactement cinq classes ? Parce que tout entier a un unique reste entre 00 et 44 : c'est l'énoncé suivant.

Continuer : Combien de classes →

Étape 2 sur 5

Combien de classes

PropriétéDescription de ℤ/nℤ

Soit nn un entier naturel, n≥2n \geq 2.

  1. Pour tous entiers relatifs aa et bb : a‾=b‾\overline{a} = \overline{b} si et seulement si a≡b [n]a \equiv b \ [n].
  2. Z/nZ={0‾,1‾,…,n−1‾}\mathbb{Z}/n\mathbb{Z} = \{\overline{0}, \overline{1}, \dots, \overline{n-1}\}, et ces nn classes sont deux à deux distinctes.

Démonstration

Étape 1 (point 1). Si a‾=b‾\overline{a} = \overline{b}, alors a∈a‾a \in \overline{a} (car a≡a [n]a \equiv a \ [n], « Opérations sur les congruences »), donc a∈b‾a \in \overline{b}, c'est-à-dire a≡b [n]a \equiv b \ [n]. Réciproquement, si a≡b [n]a \equiv b \ [n], alors pour tout entier cc : c≡a [n]c \equiv a \ [n] équivaut à c≡b [n]c \equiv b \ [n] (transitivité et symétrie, « Opérations sur les congruences »). Donc a‾=b‾\overline{a} = \overline{b}.

Étape 2 (point 2). Tout entier aa est congru à son reste r∈{0,…,n−1}r \in \{0, \dots, n - 1\} (« Congruence et reste », point 2), donc a‾=r‾\overline{a} = \overline{r}. Si 0≤r<s≤n−10 \leq r < s \leq n - 1, alors 0<s−r<n0 < s - r < n, donc n∤s−rn \nmid s - r (« Propriétés de la divisibilité », point 3), soit r≢s [n]r \not\equiv s \ [n], et r‾≠s‾\overline{r} \neq \overline{s} d'après le point 1.

Vérifie : Le bon représentant

Dans Z/9Z\mathbb{Z}/9\mathbb{Z}, laquelle de ces classes est égale à 40‾\overline{40} ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :5‾\overline{5}

Faux.

40−5=3540 - 5 = 35 n'est pas un multiple de 99. Erreur de signe : c'est 40+5=4540 + 5 = 45 qui est un multiple de 99.

Choix B :36‾\overline{36}

Faux.

3636 est le multiple de 99 le plus proche, pas un entier congru à 4040 : 36‾=0‾\overline{36} = \overline{0}, alors que 40‾=4‾\overline{40} = \overline{4}.

Choix C :−5‾\overline{-5}

Juste.

40−(−5)=45=9×540 - (-5) = 45 = 9 \times 5, donc 40≡−5 [9]40 \equiv -5 \ [9].

Besoin d'aide ? Indice 1

Dans Z/9Z\mathbb{Z}/9\mathbb{Z}, a‾=b‾\overline{a} = \overline{b} si et seulement si 99 divise a−ba - b (description de Z/nZ\mathbb{Z}/n\mathbb{Z}).

Encore bloqué ? Indice 2

Calcule la différence entre 4040 et chaque représentant proposé.

Voir la correction complète

40=9×4+440 = 9 \times 4 + 4, donc 40‾=4‾\overline{40} = \overline{4}. Or −5=4−9-5 = 4 - 9, donc −5‾=4‾=40‾\overline{-5} = \overline{4} = \overline{40} (description de Z/nZ\mathbb{Z}/n\mathbb{Z}, point 1). On calcule ensuite avec n'importe quel représentant : le résultat ne dépend pas de ce choix, comme le dit l'énoncé suivant.

← Étape précédenteContinuer : Calculer avec des classes →

Étape 3 sur 5

Calculer avec des classes

PropriétéOpérations dans ℤ/nℤ

Soit nn un entier naturel, n≥2n \geq 2. On définit, pour tous entiers relatifs aa et bb : a‾+b‾=a+b‾eta‾×b‾=ab‾.\overline{a} + \overline{b} = \overline{a + b} \quad \text{et} \quad \overline{a} \times \overline{b} = \overline{ab}. Ces opérations ne dépendent pas des entiers choisis pour représenter les classes. Elles sont commutatives et associatives, la multiplication est distributive par rapport à l'addition, 0‾\overline{0} est neutre pour l'addition, 1‾\overline{1} est neutre pour la multiplication, et toute classe a‾\overline{a} a pour opposée −a‾\overline{-a}.

Démonstration

Étape 1 (les opérations sont bien définies). Si a‾=a′‾\overline{a} = \overline{a'} et b‾=b′‾\overline{b} = \overline{b'}, alors a≡a′ [n]a \equiv a' \ [n] et b≡b′ [n]b \equiv b' \ [n] (« Description de ℤ/nℤ »). D'après « Opérations sur les congruences », a+b≡a′+b′ [n]a + b \equiv a' + b' \ [n] et ab≡a′b′ [n]ab \equiv a'b' \ [n], donc a+b‾=a′+b′‾\overline{a + b} = \overline{a' + b'} et ab‾=a′b′‾\overline{ab} = \overline{a'b'}.

Étape 2 (les propriétés). Soient aa, bb, cc des entiers relatifs. Chaque propriété se déduit de la même propriété dans Z\mathbb{Z}. Par exemple, a‾+b‾=a+b‾=b+a‾=b‾+a‾\overline{a} + \overline{b} = \overline{a + b} = \overline{b + a} = \overline{b} + \overline{a}, et a‾×(b‾+c‾)=a(b+c)‾=ab+ac‾=a‾×b‾+a‾×c‾\overline{a} \times (\overline{b} + \overline{c}) = \overline{a(b + c)} = \overline{ab + ac} = \overline{a} \times \overline{b} + \overline{a} \times \overline{c}. De même, a‾+−a‾=0‾\overline{a} + \overline{-a} = \overline{0}. Les associativités, la commutativité de ×\times et les neutres 0‾\overline{0}, 1‾\overline{1} s'obtiennent de la même façon : on écrit chaque classe avec un représentant et on applique la propriété de Z\mathbb{Z}.

ExempleLa table de multiplication de ℤ/8ℤ

Un calcul : 5‾×6‾=30‾=6‾\overline{5} \times \overline{6} = \overline{30} = \overline{6}, car 30=8×3+630 = 8 \times 3 + 6. Voici toute la table, chaque classe notée par son reste :

×\times 0‾\overline{0} 1‾\overline{1} 2‾\overline{2} 3‾\overline{3} 4‾\overline{4} 5‾\overline{5} 6‾\overline{6} 7‾\overline{7}
0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0}
1‾\overline{1} 0‾\overline{0} 1‾\overline{1} 2‾\overline{2} 3‾\overline{3} 4‾\overline{4} 5‾\overline{5} 6‾\overline{6} 7‾\overline{7}
2‾\overline{2} 0‾\overline{0} 2‾\overline{2} 4‾\overline{4} 6‾\overline{6} 0‾\overline{0} 2‾\overline{2} 4‾\overline{4} 6‾\overline{6}
3‾\overline{3} 0‾\overline{0} 3‾\overline{3} 6‾\overline{6} 1‾\overline{1} 4‾\overline{4} 7‾\overline{7} 2‾\overline{2} 5‾\overline{5}
4‾\overline{4} 0‾\overline{0} 4‾\overline{4} 0‾\overline{0} 4‾\overline{4} 0‾\overline{0} 4‾\overline{4} 0‾\overline{0} 4‾\overline{4}
5‾\overline{5} 0‾\overline{0} 5‾\overline{5} 2‾\overline{2} 7‾\overline{7} 4‾\overline{4} 1‾\overline{1} 6‾\overline{6} 3‾\overline{3}
6‾\overline{6} 0‾\overline{0} 6‾\overline{6} 4‾\overline{4} 2‾\overline{2} 0‾\overline{0} 6‾\overline{6} 4‾\overline{4} 2‾\overline{2}
7‾\overline{7} 0‾\overline{0} 7‾\overline{7} 6‾\overline{6} 5‾\overline{5} 4‾\overline{4} 3‾\overline{3} 2‾\overline{2} 1‾\overline{1}

Ces règles de calcul ont un nom, que tu verras au chapitre des structures.

AttentionUn produit nul modulo 8

Dans Z/8Z\mathbb{Z}/8\mathbb{Z}, 2‾×4‾=0‾\overline{2} \times \overline{4} = \overline{0}, alors que 2‾≠0‾\overline{2} \neq \overline{0} et 4‾≠0‾\overline{4} \neq \overline{0}. Même 4‾×4‾=0‾\overline{4} \times \overline{4} = \overline{0}. La règle « un produit nul a un facteur nul » est fausse modulo un entier composé. N'en conclus rien sans un module premier.

← Étape précédenteContinuer : Les classes inversibles →

Étape 4 sur 5

Les classes inversibles

Relis la table : 1‾\overline{1} apparaît dans les lignes de 1‾\overline{1}, 3‾\overline{3}, 5‾\overline{5} et 7‾\overline{7}, jamais dans celles de 2‾\overline{2}, 4‾\overline{4}, 6‾\overline{6}. Par exemple, 3‾×3‾=9‾=1‾\overline{3} \times \overline{3} = \overline{9} = \overline{1}. Or 11, 33, 55 et 77 sont exactement les restes premiers avec 88. Pourquoi est-ce vrai ? Trouver uu tel que au≡1 [n]au \equiv 1 \ [n], c'est écrire au+nv=1au + nv = 1 : on reconnaît Bézout.

PropriétéClasses inversibles de ℤ/nℤ

Soient nn un entier naturel, n≥2n \geq 2, et aa un entier relatif. La classe a‾\overline{a} est inversible dans Z/nZ\mathbb{Z}/n\mathbb{Z}, c'est-à-dire qu'il existe une classe b‾\overline{b} telle que a‾×b‾=1‾\overline{a} \times \overline{b} = \overline{1}, si et seulement si a∧n=1a \wedge n = 1.

Démonstration

Étape 1. Comme a‾×b‾=ab‾\overline{a} \times \overline{b} = \overline{ab} (« Opérations dans ℤ/nℤ »), l'égalité a‾×b‾=1‾\overline{a} \times \overline{b} = \overline{1} équivaut à ab≡1 [n]ab \equiv 1 \ [n] (« Description de ℤ/nℤ »), c'est-à-dire à l'existence d'un entier relatif kk tel que ab−1=nkab - 1 = nk, soit ab+n(−k)=1ab + n(-k) = 1.

Étape 2. Donc a‾\overline{a} est inversible si et seulement s'il existe deux entiers relatifs uu et vv tels que au+nv=1au + nv = 1 : si a‾×b‾=1‾\overline{a} \times \overline{b} = \overline{1}, on prend u=bu = b et v=−kv = -k ; si au+nv=1au + nv = 1, alors au≡1 [n]au \equiv 1 \ [n] et a‾×u‾=1‾\overline{a} \times \overline{u} = \overline{1}.

Étape 3. Par le théorème de Bézout, cette dernière condition équivaut à a∧n=1a \wedge n = 1.

Méthodeinverser une classe

Montrer que 17‾\overline{17} est inversible dans Z/40Z\mathbb{Z}/40\mathbb{Z}, puis trouver son inverse.

  1. Vérifier le PGCD. 40=2×17+640 = 2 \times 17 + 6, 17=2×6+517 = 2 \times 6 + 5, 6=1×5+16 = 1 \times 5 + 1. Le dernier reste non nul est 11, donc 17∧40=117 \wedge 40 = 1 : 17‾\overline{17} est inversible.
  2. Remonter les divisions. 1=6−5=6−(17−2×6)=3×6−17=3×40−7×171 = 6 - 5 = 6 - (17 - 2 \times 6) = 3 \times 6 - 17 = 3 \times 40 - 7 \times 17.
  3. Conclure. 17×(−7)≡1 [40]17 \times (-7) \equiv 1 \ [40], donc l'inverse de 17‾\overline{17} est −7‾=33‾\overline{-7} = \overline{33}.
  4. Contrôler. 17×33=561=14×40+117 \times 33 = 561 = 14 \times 40 + 1.

Rédaction attendue. « 17∧40=117 \wedge 40 = 1, donc 17‾\overline{17} est inversible (classes inversibles). Comme 17×(−7)+40×3=117 \times (-7) + 40 \times 3 = 1, l'inverse de 17‾\overline{17} est 33‾\overline{33}. »

Vérifie : Une classe sans inverse

Laquelle de ces classes n'est pas inversible dans Z/15Z\mathbb{Z}/15\mathbb{Z} ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :2‾\overline{2}

Faux.

2∧15=12 \wedge 15 = 1 : elle est inversible, d'inverse 8‾\overline{8}, car 2×8=16≡1 [15]2 \times 8 = 16 \equiv 1 \ [15].

Choix B :7‾\overline{7}

Faux.

7∧15=17 \wedge 15 = 1 : 7×13=91=6×15+17 \times 13 = 91 = 6 \times 15 + 1, donc 13‾\overline{13} est son inverse.

Choix C :14‾\overline{14}

Faux.

14∧15=114 \wedge 15 = 1 : 14‾=−1‾\overline{14} = \overline{-1} est son propre inverse, car (−1)×(−1)=1(-1) \times (-1) = 1.

Choix D :9‾\overline{9}

Juste.

9∧15=3≠19 \wedge 15 = 3 \neq 1 : d'après la caractérisation des classes inversibles, 9‾\overline{9} n'a pas d'inverse.

Besoin d'aide ? Indice 1

Une classe a‾\overline{a} est inversible dans Z/15Z\mathbb{Z}/15\mathbb{Z} si et seulement si a∧15=1a \wedge 15 = 1.

Encore bloqué ? Indice 2

Cherche un diviseur commun à aa et à 1515, autre que 11.

Voir la correction complète

15=3×515 = 3 \times 5. Parmi 22, 77, 1414 et 99, seul 99 est divisible par 33 ou par 55 : 9∧15=39 \wedge 15 = 3. Donc 9‾\overline{9} n'est pas inversible (classes inversibles de Z/nZ\mathbb{Z}/n\mathbb{Z}). D'ailleurs 9‾×5‾=45‾=0‾\overline{9} \times \overline{5} = \overline{45} = \overline{0}, avec 5‾≠0‾\overline{5} \neq \overline{0}.

← Étape précédenteContinuer : Un module premier →

Étape 5 sur 5

Un module premier

PropriétéLe cas de ℤ/pℤ, p premier

Soit pp un nombre premier.

  1. Toute classe non nulle de Z/pZ\mathbb{Z}/p\mathbb{Z} est inversible.
  2. Pour toutes classes a‾\overline{a} et b‾\overline{b} de Z/pZ\mathbb{Z}/p\mathbb{Z} : si a‾×b‾=0‾\overline{a} \times \overline{b} = \overline{0}, alors a‾=0‾\overline{a} = \overline{0} ou b‾=0‾\overline{b} = \overline{0}.

Démonstration

Étape 1 (point 1). Si a‾≠0‾\overline{a} \neq \overline{0}, alors a≢0 [p]a \not\equiv 0 \ [p] (« Description de ℤ/nℤ »), c'est-à-dire p∤ap \nmid a. D'après « Conséquences du théorème de Gauss » (point 1), a∧p=1a \wedge p = 1, donc a‾\overline{a} est inversible (« Classes inversibles de ℤ/nℤ »).

Étape 2 (point 2). Si a‾×b‾=0‾\overline{a} \times \overline{b} = \overline{0}, alors ab‾=0‾\overline{ab} = \overline{0} (« Opérations dans ℤ/nℤ »), donc ab≡0 [p]ab \equiv 0 \ [p] (« Description de ℤ/nℤ »), c'est-à-dire p∣abp \mid ab. D'après « Conséquences du théorème de Gauss » (point 2), p∣ap \mid a ou p∣bp \mid b, soit a‾=0‾\overline{a} = \overline{0} ou b‾=0‾\overline{b} = \overline{0}.

ExempleLa table de multiplication de ℤ/5ℤ

Modulo 55, nombre premier, chaque ligne non nulle contient 1‾\overline{1}, et aucun produit de deux classes non nulles n'est nul :

×\times 0‾\overline{0} 1‾\overline{1} 2‾\overline{2} 3‾\overline{3} 4‾\overline{4}
0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0} 0‾\overline{0}
1‾\overline{1} 0‾\overline{0} 1‾\overline{1} 2‾\overline{2} 3‾\overline{3} 4‾\overline{4}
2‾\overline{2} 0‾\overline{0} 2‾\overline{2} 4‾\overline{4} 1‾\overline{1} 3‾\overline{3}
3‾\overline{3} 0‾\overline{0} 3‾\overline{3} 1‾\overline{1} 4‾\overline{4} 2‾\overline{2}
4‾\overline{4} 0‾\overline{0} 4‾\overline{4} 3‾\overline{3} 2‾\overline{2} 1‾\overline{1}

On y lit les inverses : 1‾\overline{1} et 4‾\overline{4} sont leurs propres inverses ; 2‾\overline{2} et 3‾\overline{3} sont inverses l'un de l'autre.

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (2bac · sciences-mathematiques · mathematiques)