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