Mathématiques · Licence 1 · 4 leçons

Fiche de révision : Arithmétique et structures algébriques

L’essentiel de chaque leçon du chapitre, tel qu’il est écrit dans le cours : à relire, à imprimer, puis à vérifier par l’entraînement.

Les notions de cette fiche

Algorithme d'Euclide, PGCD et théorème de Bézout — Division euclidienne dans les entiers relatifs ; PGCD et algorithme d'Euclide ; remontée de l'algorithme donnant un couple de coefficients de Bézout ; théorème de Bézout et son cas particulier des entiers premiers entre eux ; description de TOUS les couples solutions à partir d'un couple particulier, et unique représentant normalisé ; théorème de Gauss ; équation diophantienne du premier degré à deux inconnues : condition d'existence (le PGCD divise le second membre) et ensemble complet des solutions.
Congruences et anneau des classes de reste — Congruence modulo n, compatibilité avec la somme et le produit, classes de reste et anneau Z/nZ ; critère d'inversibilité (une classe est inversible si et seulement si son représentant est premier avec n) et calcul effectif de l'inverse par Bézout ; résolution de la congruence ax ≡ c modulo n, condition d'existence et NOMBRE exact de solutions modulo n ; petit théorème de Fermat et calcul de puissances modulaires ; théorème des restes chinois sur deux modules premiers entre eux.
Polynômes : division euclidienne, racines et factorisation — Polynôme formel à coefficients réels ou complexes, degré et degré d'un produit ; division euclidienne d'un polynôme par un polynôme non nul, unicité du quotient et du reste ; racine et divisibilité par X − a, multiplicité d'une racine et caractérisation par les dérivées successives ; PGCD de deux polynômes par l'algorithme d'Euclide et identité de Bézout polynomiale ; factorisation en produit d'irréductibles sur les complexes puis sur les réels ; relations entre coefficients et racines.
Loi de composition interne et structure de groupe — Loi de composition interne, associativité, élément neutre, symétrique ; définition d'un groupe et d'un groupe abélien ; sous-groupe et caractérisation par la stabilité ; ordre d'un élément dans un groupe fini ; morphisme de groupes, noyau et image ; exemples travaillés : le groupe additif des classes de reste, le groupe multiplicatif des inversibles modulo n, le groupe des permutations d'un ensemble fini, le groupe des isométries d'une figure.

À maîtriser avant de commencer

Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.

Divisibilité et nombres premiers — Critères de divisibilité, diviseurs et multiples, décomposition en produit de facteurs premiers, fractions irréductibles.
Opérations sur les entiers — Additionner, soustraire, multiplier et diviser des entiers naturels ; priorités opératoires ; division euclidienne.
Développement et factorisation — Distributivité simple et double, identités remarquables (a + b)², (a − b)², (a + b)(a − b), factorisation par un facteur commun.
Équations du second degré — Discriminant, racines réelles, forme canonique, forme factorisée, signe du trinôme.
Nombres complexes — Forme algébrique, conjugué, module, argument, forme exponentielle, formules d'Euler et de Moivre, résolution dans ℂ du second degré.

Le début de la fiche

Extrait de la leçon « Algorithme d'Euclide, Bézout et l'équation ax + by = c », tel qu’il figure sur la fiche.

Ce qu'il faut retenir

$a = bq + r,\ 0 \le r < b \implies \mathrm{pgcd}(a\,;\,b) = \mathrm{pgcd}(b\,;\,r) \quad \text{(le PGCD est le dernier reste non nul)}$
$\text{Bézout : } \exists\,(u\,;\,v) \in \mathbb{Z}^2,\ au + bv = \mathrm{pgcd}(a\,;\,b) \qquad \mathrm{pgcd}(a\,;\,b) = 1 \iff \exists\,(u\,;\,v),\ au + bv = 1$
$\text{tous les couples : } \left(u_0 + k\,\frac{b}{d}\ ;\ v_0 - k\,\frac{a}{d}\right),\ k \in \mathbb{Z} \quad \text{(un seul avec } 0 \le u < \tfrac{b}{d}\text{)}$
$\text{Gauss : } a \text{ divise } bc \ \text{et}\ \mathrm{pgcd}(a\,;\,b) = 1 \implies a \text{ divise } c$
$ax + by = c \text{ a des solutions} \iff d \text{ divise } c, \qquad \mathcal{S} = \left\{\left(x_0 + k\,\tfrac{b}{d}\ ;\ y_0 - k\,\tfrac{a}{d}\right),\ k \in \mathbb{Z}\right\}$
$\mathrm{pgcd}(a\,;\,n) = 1 \implies \exists\, u,\ au \equiv 1\ [n] \quad \text{(inverse de } a \text{ modulo } n\text{, unique parmi } 0, \dots, n - 1\text{)}$

Tableau : Objet, Ce que c'est, Ce qu'il faut vérifier
Objet	Ce que c'est	Ce qu'il faut vérifier
Algorithme d'Euclide	suite de divisions euclidiennes, restes strictement décroissants	le PGCD est le dernier reste non nul, pas $0$
Couple de Bézout	$(u\,;\,v)$ avec $au + bv = d$	recalculer $au + bv$ à la fin : une remontée perd facilement un signe
Famille des couples	$\left(u_0 + k\,\tfrac{b}{d}\ ;\ v_0 - k\,\tfrac{a}{d}\right)$	le pas de $u$ est $\tfrac{b}{d}$ , celui de $v$ est $\tfrac{a}{d}$ — croisés
Représentant normalisé	l'unique couple avec $0 \le u < \tfrac{b}{d}$	il existe et il est unique parce que $\tfrac{b}{d} \ge 1$
Équation $ax + by = c$	solutions si et seulement si $d$ divise $c$	multiplier le couple de Bézout par $\tfrac{c}{d}$ , puis Gauss pour la famille
Inverse modulo $n$	$u$ tel que $au \equiv 1\ [n]$	existe si et seulement si $\mathrm{pgcd}(a\,;\,n) = 1$  ; c'est le $u$ de Bézout réduit modulo $n$

La remontée, mécaniquement. On écrit la dernière division à reste non nul sous la forme $r_{k} = r_{k - 2} - q_k\,r_{k - 1}$ , puis on remplace $r_{k - 1}$ par son expression, en gardant $r_{k - 2}$ et $r_{k - 3}$ entre parenthèses, et l'on remonte jusqu'à $a$ et $b$ . Tant qu'on n'a pas recalculé $au + bv$ avec les valeurs trouvées, le résultat n'est pas acquis.

Ce qui n'est pas dans cette leçon. L'anneau $\mathbb{Z}/n\mathbb{Z}$ et ses propriétés, le petit théorème de Fermat, le théorème des restes chinois, l'arithmétique des polynômes, la complexité exacte de l'algorithme (théorème de Lamé), et toute application au chiffrement.

La suite de la fiche (3 autres notions, les pièges à éviter et la version imprimable) est réservée à votre compte.

S’entraîner sur ces notions

Continuez dans votre compte

Créez votre compte gratuit pour lire la fiche entière et l’imprimer, ou connectez-vous pour revenir directement ici.

Créer mon compte gratuit Me connecter pour continuer

L’accès gratuit comprend les cours et exercices de votre niveau choisi.