Algèbre et Arithmétique Effectives
Université Grenoble Alpes - 2026/2027
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 2026/2027 à l'Université Grenoble Alpes.
Page Web L3MIModalités de Controle PRESENTATION DU COURS - SLIDES
Horaire et lieu des cours:
Mardi : 9h45 – 11h15 (CM) en F116 (Bâtiment F, Campus de Saint-Martin-d'Hères) — Groupe 1 et 2 (avec Annamaria Iezzi)
Mercredi : 8h – 9h30 en PC F212 (Bâtiment F, Campus de Saint-Martin-d'Hères) et 13h30 – 15h (TD) en F112 (Bâtiment F, Campus de Saint-Martin-d'Hères) — Groupe 1 (avec Annamaria Iezzi)
Mercredi : 13h30 – 15h (TD) en F111 (Bâtiment F, Campus de Saint-Martin-d'Hères) et 15h15 – 16h45 en PC F217 (Bâtiment F, Campus de Saint-Martin-d'Hères) — Groupe 2 (avec Antoine de Tarlé)
Références :
- Les pages web 2024/2025 et 2025/2026 du cours de AAE.
- 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.)
Cahier de bord :
- 08/09/2026 : 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 version soustractive et pseudo-code. Algorithme d'Euclide version moderne et pseudo-code.
PRESENTATION DU COURS - SLIDES - 09/09/2026 : TP1 et exercices 1,2 et 3 du TD1.
TP 1TD 1 - 10/09/2026 : Quelques rappels de théorie de la complexité: taille d'un entier, notation asymptotique (Grand-$O$, Grand-$\Omega$, $\Theta$), pire cas, coût des opérations d'addition, multiplication et division en la taille des entrées. Coût de l'algorithme d'Euclide version soustractive. Identité de Bézout et un exemple. Exercices 3, 4 et 5 du TD1.
TD 1 - 11/09/2026 : TP1 (jusqu'à l'exercice 8) et début du TP2.
TP 1TP 2 - 22/09/2026 : Coût de l'algorithme d'Euclide (borne supérieure sur le nombre de divisions euclidiennes et coût total). Algorithme d'Euclide étendu (version récursive) et preuve de correction.
- 23/09/2026 : Fin du TP1 et du TP2. Exercice 6 du TD1 et exercices 1 et 2 du TD2. Pour la prochaine fois, terminer le TD1.
TP 1TP 2TD 1TD 2 - 29/09/2026 : Rappels: définitions de nombre premier et composé. Lemme de Gauss (démonstration en TD). Théorème Fondamental de l'Arithmétique (avec démonstration). Rappels: définition de relation d'équivalence, classes d'équivalence et ensemble quotient. Définition de la rélation d'équivalence de congruence modulo $n$. Exemples pour $n=1,2$.
Cours 4 - 30/09/2026 : TP3 (à terminer à la maison). Correction de l'exercice 2 et 3 du TD2 et des exercices 1, 2 et 3 du TD3. Pour la prochaine fois faire l'exo 4 du TD2 et l'exo 4 du TD3.
TP 3TD 2TD 3 - 06/10/2026 : Notation $\mathbb Z/n\mathbb Z.$ 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. $\mathbb Z/n\mathbb Z$ est un anneau commutatif unitaire, mais pas toujours un corps (exemples). Définition d'élément inversible dans $\mathbb Z/n\mathbb Z$.
Cours 5 - 07/10/2026 : Début TP4. Exercices 1,2,3,6 du TD 4.
TP 4TD 4 - 13/10/2026 :
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. Fonction indicatrice d'Euler. Si $p$ est premier alors $\mathbb Z/p\mathbb Z$ est un corps.
Résolution de congruences linéaires (existence des solutions et calcul des solutions).
Cours 6 - 14/10/2026 : Continuation TP4. Exercices 7 du TD4 et exercices 1 et 2(a) du TD5.
TP5TD4TD5