Algèbre et Arithmétique Effectives
Université Grenoble Alpes - 2025/2026
Cette page est dédiée au cours d'Algèbre et Arithmétique Effectives (L3 Informatique, Parcours Mathématiques et Informatique) de l'année académique 2025/2026 à l'Université Grenoble Alpes.
Page Web L3MIModalités de Controle PRESENTATION DU COURS - SLIDES
Références :
- La page web de M. Bruno Grenet (pour le cours de AAE en 2022/2023 et 2023/2024).
- Cours d’algèbre, Michel Demazure, Paris : Cassini, 2ème édition (2008). (Plusieurs exemplaires disponibles à la bibliothèque Joseph Fourier.)
- A Computational Introduction to Number Theory and Algebra, Victor Shoup, Cambridge University Press, 2nd edition, 2009. (Téléchargeable librement en cliquant sur le lien.)
- Modern Computer Algebra, Joachim von zur Gathen et Jürgen Gerhard, Cambridge University Press, 3rd edition (2013). (Plusieurs exemplaires disponibles à la bibliothèque Joseph Fourier.)
Informations pour les étudiants
Cahier de bord :
- 09/09/2025 : Présentation du cours. Rappels de divisibilité: $a$ divise $b$, diviseur commun, plus grand commun diviseur (pgcd), nombres premiers entre eux. Algorithme originaire d'Euclide par soustraction et pseudo-code. Algorithme d'Euclide classique et pseudo-code. Identité de Bézout.
PRESENTATION DU COURS - SLIDESCours 1 - 10/09/2025 : TP1 : pour la prochaine fois, s'assurer d'avoir complété les premiers 8 exercices (jusqu'à l'algorithme d'Euclide classique). TD1
TP 1TD 1. - 16/09/2025 : Quelques rappels de théorie de la complexité: taille d'un entier, notation asymptotique (Grand-$O$, Grand-$\Omega$, $\Theta$). Coût de l'algorithme d'Euclide (borne supérieure sur le nombre de divisions euclidiennes et coût total). Variante de l'algorithme binaire du PGCD. Algorithme d'Euclide étendu (version récursive) et preuve de correction.
Cours 2 - 17/09/2025 : Fin du TP1, début du TP2. Pour la prochaine fois s'assurer d'avoir complété le TD1.
TP 1TP 2TD 1 - 23/09/2025 : Rappels: définitions de nombre premier et composé. Lemme de Gauss (avec démonstration). Théorème Fondamental de l'Arithmétique (avec démonstration). Rappels: définition de relation d'équivalence, classes d'équivalence et ensemble des classes d'équivalence. Définition de rélation d'équivalence modulo $n$. Exemples pour $n=1,2$. Notation $\mathbb Z/n\mathbb Z.$
Cours 3 - 24/09/2025 : Fin du TP2, début du TP3. Début du TD 2 (Exercices 1,3,5,6,7).
TP 2TP 3TD 2 - 30/09/2025 : Théorème: pour toute classe d'équivalence de $\mathbb Z/n\mathbb Z$ il existe un représentant canonique entre 0 et $n-1$, qui est donné par le reste de la division euclidienne. Opérations d'addition et multiplication sur $\mathbb Z/n\mathbb Z$. Démonstration qu'elles sont bien définies. Propriétés des opérations. Définition d'élément inversible dans $\mathbb Z/n\mathbb Z$. Proposition: $a$ est inversible dans $\mathbb Z/n\mathbb Z$ si et seulement si pgcd$(a,n)=1$. Algorithme pour calculer l'inverse d'un élément dans $\mathbb Z/n\mathbb Z$.Exemples sur le calcul de l'inverse d'un élément de $\mathbb Z/n\mathbb Z$. L'ensemble $\left(\mathbb Z/n\mathbb Z\right)^{\times}$ des éléments inversibles. Si $p$ est premier alors $\mathbb Z/p\mathbb Z$ est un corps.
Cours 4 - 01/10/2025 : Fin du TP3. Exercice 8 du TD 2. Exercices 1,2,3,4,5,6 du TD 3
TP 3TD 2TD 3 - 07/10/2025 : Résolution de congruences linéaires (existence des solutions et calcul des solutions). Résolution d'un système de congruences linéaires: algorithme des restes chinois et preuve de correction.
Cours 5 - 08/10/2025 : TP4. Fin TD 3
TP 4TD 3 - 14/10/2025 :
Définition de groupe. Exemples. Ordre d'un groupe. Théorème de Lagrange (version 1), avec démo. Définition de sous-groupe d'un groupe. Exemples. Proposition pour montrer qu'un sous-ensemble non vide est un sous-groupe. Le sous-groupe engendré par un élément. L'ordre d'un élément. Définition de groupe cyclique. Exemples de groupes cycliques et non cycliques.
Cours 6 - 15/10/2025 : Fin TP4, début TP5. Exercices 1 et 2 du TD4.
TP5TD4 - 21/10/2025 : Contrôle continu.
CC - 22/10/2025 : Fin TP5. Fin TD 4.
TP 5TD 4 - 04/11/2025 : Relation de congruence modulo un sous-groupe et groupe quotient. Théorème de Lagrange (version 2). Introduction aux homomorphismes de groupes.
Cours 7 - 05/11/2025 : Définition d'homomorphisme de groupes, image et noyau. Exemples. Quelques remarques et propositions sur les homomorphismes de groupes. Définition d'isomorphisme. Exemples. Premier théorème d'isomorphisme (de groupes), avec démonstration.
Début TP6.
Cours 8TP6 - 06/11/2025 : Exemple d'application du premier théorème d'isomorphisme. Définitions d'anneau, corps, diviseurs de zéro, anneau intègre. Exemples. Définition d'idéal d'un anneau. Relation de congruence modulo un idéal et anneau quotient. (Les notes du cours seont publiée mardi 11 novembre).
Cours 9 - 18/11/2025 : Définition d'homomorphisme d'anneaux, image et noyau. Quelques remarques et propositions sur les homomorphismes d'anneaux. Définition d'isomorphismes. Premier théorème d'isomorphisme (d'anneaux).
Cours 10 - 25/11/2025 : Version du théorème des restes chinois en termes d'isomorphismes d'anneaux. Exemples. Définition de corps fini. $K[x]$, l'anneau de polynômes sur un corps et ses opérations. Eléments inversibles de $K[x]$. Définition d'élément irréductible d'un anneau intègre. Exemples dans $\mathbb Z$ et $K[x]$. $K[x]$ est un anneau euclidien: division euclidienne de deux polynômes. L'idéal $I=(P)$ engendré par un polynôme $P$ et l'anneau quotient $\frac{K[x]}{(P)}$. Si $P\neq 0$, alors l'ensemble $\frac{K[x]}{(P)}$ est en bijection avec l'ensemble des polynômes de degré $<\deg(P)$ (démonstration).
Cours 11 - 02/12/2025 : Exemple de quotient d'un anneau de polynômes. Éléments inversibles de $\frac{K[x]}{(P)}$. Proposition : $\frac{K[x]}{(P)}$ est un corps si et seulement si $P$ est irréductible dans $K[x]$. Notation $\mathbb F_p$. Définition de caractéristique d'un anneau. Proposition : la caractéristique d'un anneau intègre est $0$ ou un nombre premier (avec démonstration). Proposition : un corps fini a un nombre d'éléments égal à une puissance d'un nombre premier (avec démonstration). Proposition : Si $P$ est irréductible de degré $n$, alors $\frac{K[x]}{(P)}$ est un corps avec $p^n$ éléments (avec démonstration). Pour tout nombre premier $p$ et tout entier $n>0$, il existe un corps avec $p^n$ éléments et tous les corps avec $p^n$ éléments sont isomorphes (sans démonstration). Notation $\mathbb F_{p^n}$. Exemple.
Cours 12