Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
295 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Enseigner le pgcd

Envoyé par Homo Topi 
Enseigner le pgcd
l’an passé
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 ?

Je vous jure que je saurai faire de l'analyse réelle un jour !



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par AD.
Re: Enseigner le PGCD
l’an passé
Par définition, $d$ est PGCD de $a$ et $b$ si et seulement si $d$ divise $a$ et $b$, et tout diviseur commun de $a$ et $b$ divise $d$. Autrement dit, si et seulement si l'ensemble des diviseurs de $d$ est égal à l'ensemble des diviseurs communs de $a$ et $b$.

Dans l'algorithme d'Euclide, on note $r_n$ les restes successifs avec $r_0=a$ et $r_1=b$. Il y a un invariant de boucle qui est l'ensemble des diviseurs communs de deux restes successifs. Par ailleurs l'algorithme termine avec un $r_N=0$. Ces deux choses sont très faciles à voir. Ceci montre que $r_{N-1}$ est PGCD de $a$ et $b$ puisque l'ensemble des diviseurs communs de $a$ et $b$ est égal à l'ensemble des diviseurs communs de $r_{N-1}$ et $0$, qui est l'ensemble des diviseurs de $r_{N-1}$.

Ni groupe, ni anneau, ni idéal.

Euclide étendu donne l'identité de Bézout.
Re: Enseigner le PGCD
l’an passé
Citation

Il faudra traiter à part le cas du PGCD de 0 et d'un entier, mais ça, ce n'est pas un gros problème.

Surtout pas !!!!
Re: Enseigner le PGCD
l’an passé
Oui, en principe, la seule chose que je ne sais pas encore démontrer (ne pas souffler la réponse, je vais y réfléchir), c'est pourquoi l'ensemble des diviseurs communs ne change jamais quand on avance dans l'algorithme d'Euclide. Ça ne devrait pas être trop compliqué...

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Enseigner le PGCD
l’an passé
Tant que $r_n\neq 0$,
$$r_{n-1}= q_nr_n +r_{n+1} \quad\text{avec}\ 0\leq r_{n+1} < |r_n|\;.$$
Re: Enseigner le PGCD
l’an passé
GaBuZoMeu écrivait : [www.les-mathematiques.net]
[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
-------------------------------------------------------
Beeeeeeeeeeennn... En principe, je suis d'accord avec toi.

Mais justement, dans mon livre de L1, avec la définition du PGCD par $a \mathbb{Z} + b \mathbb{Z} = m \mathbb{Z}$, ils peuvent définir un PGCD de $(0,n)$. Alors effectivement, de 1 ça n'a aucun intérêt, et de 2 cette définition "ensembliste" ne se généralise pas correctement à tous les anneaux dans lesquels on peut définir un PGCD (cf la définition que j'ai donnée, sortie de mon livre de L3, la définition "classique"). C'est tordu, mais ça me conforte dans le choix de ne pas prendre cette définition pour le PGCD (d'ailleurs, le Gourdon utilise la même, les livres de Gourdon me déçoivent de plus en plus)

(et je commence à faire de moins en moins confiance en le moindre bouquin de maths... raison de plus de refaire tous ses cours soi-même, comme je le fais depuis que j'ai rejoint le forum...)

Je vous jure que je saurai faire de l'analyse réelle un jour !



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: Enseigner le PGCD
l’an passé
"L'ensemble des diviseurs d'un PGCD de $a$ et $b$ est égal à l'ensemble des diviseurs communs de $a$ et $b$" définit sans ambiguïté ce qu'est un PGCD de $a$ et $b$, y compris quand $a$ ou $b$ ou même les deux sont nuls.
Re: Enseigner le PGCD
l’an passé
Ah, c'était de "traiter à part" que tu parlais. J'avais mal interprété.

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Enseigner le pgcd
l’an passé
avatar
Bonjour Homo Topi,

Le pgcd (celui dont tu parles, le pgcd positif) de a et b est le plus grand diviseur commun de a et b dans $\N$. Le plus grand pour la relation d'ordre naturelle dans ce contexte, c'est-à-dire la divisibilité. Tu l'as écrit.

GaBuZoMeu en a donné deux reformulations immédiates, une troisième reformulation immédiate est de dire que le pgcd de a et b est la borne inférieure (toujours dans N muni de la divisibilité) de {|a|,|b|}. Ni groupe, ni anneau, ni idéal, mais en sus la remarque que l'expression "pgcd" est déjà une définition, en présenter une reformulation comme "la" définition ne me semble pas sain.

Comme tu l'avais bien vu et comme le précise GaBuZoMeu, l'algorithme d'Euclide te donne l'existence. C'est direct, il n'y a ni subtilité ni difficulté théorique. Mais ce n'est pas la seule façon de faire : on peut aussi passer par la décomposition en facteurs premiers si on démontre celle-ci à l'aide de la preuve de Zermelo que GG a posté il n'y a pas très longtemps sur le forum.



Edité 1 fois. La derni&egrave;re correction date de l&rsquo;an pass&eacute; et a &eacute;t&eacute; effectu&eacute;e par Nîmes-man.
Re: Enseigner le pgcd
l’an passé
Bonjour,

Concernant ce sujet voir l’article de Pierre Samuel ‘Sur l’organisation d’un cours d’arithmétique’ L’enseignement mathématiques,1967 (disponible sur www)
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 145 934, Messages: 1 455 585, Utilisateurs: 27 457.
Notre dernier utilisateur inscrit wisloch.


Ce forum
Discussions: 2 667, Messages: 56 652.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page