Justification et démonstration

Licence1: teste sur un exemple et rends toi compte par toi-même en utilisant la propriété de ta question 2)


Exemple:
pgcd(21,27)

Question subsidiaire : quel est le pgcd de 0 et 0 ?

Il n'y a absolument aucun débat. Il suffit d'appliquer la définition que j'ai rappelée.

Ce qui donne la réponse à la question du pgcd de 0 et 0, sans contestation possible.
La réponse est ...

Je vais finir par croire que tu ne sais (ou ne veux) pas lire, en particulier les définitions.

En fait, c'est n'importe quel nombre non nul qui divise 0.

Ca, c'est la définition foireuse. Le seule, la vraie, c'est celle que j'ai donnée (robuste et tout terrain, valable par exemple pour un anneau commutatif intègre quelconque).
La relation d'ordre (ou plus exactement de préordre) qui compte pour les questions de divisibilité, c'est bien évidemment la relation de divisibilité.
Faut se tenir au courant, Fin de Partie ! :-D

Ce qui est bien avec FdP c'est que cela permet de tester une argumentation avec un étudiant de mauvaise foi refusant d'admettre ses erreurs. La triste conclusion c'est qu'on ne peut visiblement rien en tirer.

$0 \mathbb{Z}+0 \mathbb{Z}=0 \mathbb{Z}$ donc $\mathrm{pgcd}(0;0)=0$.

Définition du PGCD dans le manuel de TS Math'x, éditeur Didier:
Si a et b sont des entiers non tous les deux nuls. L'ensemble des diviseurs communs à a et b admet un plus grand élément.

Ben oui, les lycéens sont encore trop petits pour avoir droit à la vraie définition du pgcd. Celle qui fait qu'on n'a pas besoin de redonner une autre définition ad hoc pour les polynômes à une ou plusieurs variables, pour les anneaux d'entiers de corps de nombres etc.

Mettons que 0 est divisible par n'importe quel nombre.

Par exemple, $0$ est divisible par $1$ et$1$ aux dernières nouvelles est plus grand que $0$ donc le pgcd de $0$ et de $0$ ne peut pas être $0$ avec la définition que j'ai donnée plus haut. B-)-

La relation de divisibilité, c'est ça : $a\mid b$ (lire $a$ divise $b$) veut dire qu'il existe $c$ tel que $b=a\,c$.
Sur $\N$, ça fait une relation d'ordre (partiel).
La définition vraiment opératoire du pgcd, celle qu'on utilise quand on fait sérieusement de l'arithmétique (pas seulement de l'arithmétique des entiers naturels, mais aussi l'arithmétique des polynomes, etc.) est celle que j'ai rappelée : $d$ est un pgcd quand c'est un diviseur commun qui est le plus grand des diviseurs communs pour l'ordre donné par cette relation de divisibilité : pour tout diviseur commun $c$, on a $c\mid d$.

_{(En général la relation de divisibilité est en fait un préordre, mais ne rentrons pas dans ces détails ici).}

Il y a beaucoup de raisons qui font que c'est vraiment la bonne définition de pgcd. Une de ces raisons, assez mineure mais non vide, est qu'il n'y a pas besoin de faire d'exception : le pgcd de 0 et 0 a bien un sens, c'est 0.

Disons qu'on donne cette définition au lycée et au collège (et même en classe préparatoire) parce c'est plus simple à raconter (et ça correspond à l'usage ancien). Ce n'est pas faux bien sûr (à condition de faire une exception pour $0$) , parce qu'il se trouve que si $b$ est non nul et si $a\mid b$, alors $a\leq b$.
Mais on fait remarquer que l'ensemble des diviseurs du pgcd de $a$ et $b$ est égal à l'ensemble des diviseurs communs de $a$ et $b$. C'est ça la propriété fondamentale (utilisée pour montrer que l'algorithme d'Euclide calcule bien le pgcd ) et cette propriété fondamentale est en fait une paraphrase de la définition du pgcd que j'ai indiquée.

Il se trouve que je n'ai aucune moralité. B-)-

C'est en tout cas une définition simple et efficace qui se généralise à tous les anneaux principaux.

Licence 1 a écrit:

Mais du coup, ce qu'on a vu au collège et lycée n'est pas tout à fait exact (ou incomplet) lorsqu'on définit le PGCD seulement comme étant le plus grand commun diviseur ?

Du coup, je me demande si je ne vais pas donner la définition suivante en terminale :
1) $\mathrm{pgcd}(0;0)=0$.
2) Si $a \neq 0$ ou $b \neq 0$, $\mathrm{pgcd}(a,b)$ est la plus petite combinaison linéaire de $a$ et $b$ dans $\mathbb{N}^*$.

Ce sera bien pratique pour démontrer le théorème de Bézout.

C'est plutôt $\{x\in\mathbb{N}^* \text{ tel qu'il existe u,v entiers tels que } x=au+bv\}$.
Si $\mathrm{pgcd}(a,b)=1$, le minimum vaut $1$ par définition...
S'il existe $u$ et $v$ tels que $au+bv=1$, alors ce minimum vaut $1$ qui est le plus petit élément de $\mathbb{N}^*$.

Avec la définition classique, sauf erreur, le point délicat à démontrer est l'implication que j'ai rappelée ci-dessus.
Avec ta définition, il doit bien avoir un point délicat à démontrer. :-D

Licence 1 écrivait: a écrit:

2) Qu'est ce qui justifie / démontre que l'algorithme des soustractions successives permet d'obtenir le PGCD de a et de b ?

On utilise un invariant de boucle.

Ecrivons l'algorithme comme suit :

SOUS_SUCC(a;b) := 
   Si a>b alors SOUS_SUCC(b;a)
   Sinon si a==0 alors renvoyer b
   Sinon SOUS_SUCC(a,b-a)

Ou comme suit :

SOUS_SUCC(a;b) := 
   Tant que a>0
        Si a>b alors échanger les valeurs de a et b
        Sinon b:=b-a
   Renvoyer b

On remarque que, même si les valeurs de a et b changent, le pgcd de a et b est une constante tout au long de l'algorithme.
En notant $a_0$ et $b_0$ les valeurs initiales de a et b, et $a_f$ et $b_f$ les valeurs finales, comme le pgcd est constant, on écrit que :
$$\text{pgcd}(a_0,b_0)=\text{pgcd}(a_f,b_f)=\text{pgcd}(0,b_f)=b_f $$

Donc la valeur renvoyée à la fin ($b_f$) est bien le pgcd des valeurs initiales de a et b.

Je n'en vois pas mais je suis sûr que tu vas en trouver un. a écrit:

Délicat pour un élève de terminale S.

Dans ce que je rappelais ci-dessus, la démonstration de la réciproque, ua+vb=1 entraîne pgcd(a,b)=1 doit être connue d'un élève de terminale (je l'espère) mais le sens direct est bien plus délicat.

Il faut que je réfléchisse au point délicat probable qu'entraine ta définition de pgcd.

Je vais mettre mon nez dans cette discussion pour la première question de Licence1.

L'antyphérèse (méthode des soustractions successives) est antérieure à Euclide, si Pythagore a existé, il la connaissait. Dans les éléments, Euclide l'utilise pour chercher la partie aliquote de deux grandeurs, intuitivement le plus grand segment qui divise deux segments de longueur donnée. Le réinvestissement de cette technique dans la recherche du PGCD est alors compréhensible ; rappelons que les éléments traitent de grandeurs mais pas de nombres. Bien entendu, dans la démarche initiale, il y a une hypothèse implicite : le processus s'arrête ! c'est probablement l'étude du pentagone régulier qui a mené à l'idée que le processus ne s'arrêtait pas de façon systématique.

Dans la figure ci-dessous, la longueur $c'_0 = A_2A_5$ est le côté du pentagramme, la longueur $c_0 = A_1A_2$ celle du côté du pentagone et la longueur $c'_1 = A_1A'_1 = c'_0 - c_0$ celle du pentagramme d'ordre inférieur. Il aisé (même si cela a pu prendre du temps) de s'apercevoir que le processus ne s'arrête pas et que les grandeurs $c_0$ et $c'_0$ n'ont pas de partie aliquote.

Bruno

Description de l'algorithme ci-dessus.
Entrée : un couple d'entiers. Sortie : le pgcd.
Si un des entiers du couple est $0$, retourner l'autre.
Tant que ce n'est pas le cas, remplacer le couple par celui formé du plus petit (au sens large) et de la différence entre le plus grand et le plus petit.

Faire marcher l'algorithme sur le couple $(0,0)$.

Gai Requin:

N'est-ce pas délicat de montrer pour un élève de terminale S, par exemple, qu'avec ta définition du pgcd (le minimun strictement positif des "combinaisons linéaires de a et b") qu'on a d divise a>0 et b>0?

Une démonstration possible:

Il existe $q,r$ tels que $a=qd+r$ avec $r=0$ ou $0<r<d$ où $d=pgcd(a,b)$

Puisque $d=pgcd(a,b)$ il existe donc $u,v$ entiers tels que $au+bv=d$
donc: $r=a-qd=a-q(au+bv)=a(1-qu)+bqv$ ce qui entraine que $r=0$ autrement cela contredirait la définition de $d$.

@ev : j'ignore si l'individu Pythagore a existé, par contre je suis convaincu de l'existence de l'école de pensée pythagoricienne.

Bruno