Enseigner le pgcd

Je suis en train de faire des révisions d'arithmétique, parce que ce n'est pas vraiment un de mes points forts. Dans mon bouquin, je me suis rendu compte d'un truc qui me dérange d'un point de vue pédagogique. En gros, ils font un topo assez rapide sur les groupes, les anneaux et les idéaux, pour s'en servir au moment de définir le PGCD et d'en montrer les propriétés fondamentales.

Pourquoi ça me dérange ? Parce que c'est dans un livre de première année. Des tutorats en première année, j'en ai fait pendant plusieurs années, et les notions de groupe, d'anneau, de corps etc, la majorité d'entre eux ne les maîtrise largement pas assez pour qu'on s'en serve pour court-circuiter des démonstrations comme ça. Ce que ces étudiants avaient vu, c'était un topo assez rapide sur les groupes, les anneaux et les corps, histoire de pouvoir rapidement commencer l'algèbre linéaire. Mais quand je dis topo rapide, je veux dire vraiment rapide, 2h de cours à tout casser en début d'année. Après ça, ils trouvent que la structure d'espace vectoriel, c'est hyper compliqué, et ce n'est pas étonnant... et des livres qui font exactement ça, un topo très sommaire sur les structures algébriques pour s'en servir avant que les étudiants aient assez de recul pour tout comprendre, j'en ai vu PLEIN. Je n'aime pas le concept du tout.

Donc en fait, ce que j'aimerais, c'est que vous m'aidiez à trouver une présentation plus élémentaire du PGCD que celle dans mon bouquin. Je vais lister rapidement comment ils font :

Théorème-Définition 1 : il existe un unique entier naturel $m$ tel que $a \mathbb{Z} + b \mathbb{Z} = m \mathbb{Z}$, et on l'appelle le PGCD de $a$ et $b$.

Ici, on utilise le fait que $\mathbb{Z}$ soit principal pour dire que ses idéaux sont tous de la forme $n \mathbb{Z}$ et que la somme de deux idéaux est encore un idéal. C'est ici qu'on démontre l'existence du PGCD. L'unicité est triviale à démontrer même sans les idéaux.

Proposition 2 : $d$ est un diviseur commun de $a$ et $b$ si, et seulement si, $d$ divise leur PGCD.

Ce résultat est nécessaire pour démontrer le lemme suivant, en plus de justifier l'appellation "plus grand" diviseur commun (au sens de la relation de divisibilité)

Lemme 3 : Si $b \neq 0$ et si $a=bq +r$ est la division euclidienne de $a$ par $b$, alors PGCD$(a,b)$ = PGCD$(b,r)$.

Ce résultat est nécessaire pour démontrer le théorème suivant.

Théorème 4 (Algorithme d'Euclide) : Soient $a \in \mathbb{N}$ et $b \in \mathbb{N}^*$. On définit la suite $(r_n)_{n \in \mathbb{N}}$ par : $r_0 = a$, $r_1 = b$, et pour tout $n \in \mathbb{N}$, $r_{n+2}$ est le reste dans la division euclidienne de $r_n$ par $r_{n+1}$. Alors la suite $(r_n)_n$ devient stationnaire à $0$. Plus précisément, il existe $M = \min\{n \in \mathbb{N} \mid r_n = 0\}$ et on a alors $r_{M-1} =$ PGCD$(a,b)$.

On peut sans aucun problème démontrer que la suite stationne à $0$ sans utiliser l'artillerie lourde des anneaux et des idéaux, donc l'existence de $M$ est facile à obtenir. Cependant, je crois qu'on ne peut pas "remonter" l'algorithme d'Euclide sans utiliser le Lemme 3.

---

Alors, dans la même série de livres, il y a un livre d'Algèbre L3. Dans ce livre-là, ils reparlent du PGCD, mais dans le cadre général de la théorie des anneaux... sauf que pour une bonne partie des propriétés, ils ne les démontrent pas, parce que ça a déjà été fait dans le livre de L1. Cependant, dans le livre de L3, ils définissent le PGCD un peu différemment. Je remets ça ici.

Définition : Soit $A$ un anneau (commutatif unitaire) intègre. Soient $x,y \in A \setminus \{0\}$. On dit que $d$ est un PGCD de $x$ et $y$ si c'est un diviseur commun de $x$ et $y$ et si tout autre diviseur commun de $x$ et $y$ divise $d$.

Cette définition, à condition de l'écrire spécifiquement dans $\mathbb{Z}$, me paraît nettement plus abordable pour des étudiants qui débutent. En principe, il faudrait la modifier un peu : pour que le PGCD puisse être unique (puisqu'avec cette définition, deux PGCD de $x$ et $y$ peuvent être distincts, ils seront associés dans $A$ mais c'est tout), on exige que ce soit un entier naturel (et ça recoupe avec la définition $a \mathbb{Z} + b \mathbb{Z} = m \mathbb{Z}$, d'ailleurs). Il faudra traiter à part le cas du PGCD de $0$ et d'un entier, mais ça, ce n'est pas un gros problème.

Le problème est plutôt le suivant : avec cette définition, il faut démontrer que le PGCD de deux entiers (non nuls, pour l'instant) existe. L'unicité est simple : si $d$ et $d'$ sont deux PGCD de $x$ et $y$, alors on a $d \mid d'$ et $d' \mid d$, donc $d' = \pm d$, mais comme les deux sont des entiers naturels, on a $d'=d$. Un étudiant de première année peut comprendre ça sans trop d'effort.

Pour l'existence, l'idée que j'avais, c'est que l'algorithme d'Euclide fournit le PGCD. Enfin, il faudrait démontrer que le terme $r_{M-1}$ est un PGCD. Mais pour démontrer mon théorème sur l'algorithme d'Euclide, je crois qu'il faut utiliser le Lemme 3 (qui, de par son énoncé, nécessite de savoir que le PGCD existe toujours...), qui se démontre avec la Proposition 2, qui se démontre avec les idéaux tout comme le Théorème 1. Je suis dans l'impasse.

Résumé : Je cherche une démonstration de l'existence du PGCD, qui n'utilise aucune notion de groupe, d'anneau, d'idéal. Quelqu'un a une piste ?