PGCD équivalence de définitions

[savancosinus]

Bonjour,

je voudrais montrer l'équivalence des définitions suivantes du PGCD dans Z :

1ère définition : le PGCD de a et de b est le plus grand élément de (donc au sens de l'inégalité).

2ème définition : le PGCD est le Plus Grand Commun Diviseur de a et de b (donc cette fois au sens de la relation "divise").

2 => 1 est facile puisque : (n divise m) implique (n inférieur ou égal à m).

1 => 2 : je n'y arrive pas :dodo:

[Judoboy]

Pour la def. 2 il faut préciser qu'on prend le PGCD positif (y en a un autre négatif qui vérifie les conditions de la 2ème définition).

Bon après on peut s'occuper que des entiers positifs, et là l'équivalence est complètement triviale une fois que tu sais qu'il existe un diviseur commun à a et à b maximal pour la relation divise ; cet élément doit nécessairement coïncider avec le plus grand élément pour la relation d'ordre usuelle sur Z.

Au pire du pire tu fais par la contraposée (si x est le plus grand élément pour la relation divise c'est le plus grand pour la relation d'ordre usuelle ; réciproquement si x est le plus grand élément pour la relation usuelle et pas pour la relation divise ça va déconner).

Bon je sais pas si c'est très clair mais je suis crevé là, l'idée c'est que dans les 2 defs on cherche un élément particulier parmi ceux qui divisent a et b, et en fait si les 2 définitions coïncident pas tu vas aboutir à une contradiction.

[savancosinus]

Merci,

Effectivement c'était pas bien compliqué, en fait je m'y prenais mal :dodo:

Et tu as raison dans la deuxième définition il faut bien préciser "positif".

Bon j'écris quand même ce que j'ai fait :

(1) Le PGCD définit dans la première définition, noté , divise a et b.
en prenant la seconde définition, qui est :
Le PGCD, noté cette fois-ci , divise a et b et tout entier d divisant a et b divise
on en déduit que divise
et donc

(2) Le PGCD définit dans la seconde définition divise a et b, donc par définition du PGCD (première définition) on a :

d'où l'égalité des "deux PGCD" et l'équivalence des définitions.


Je ne sais pas si c'est très clair, mais ça m'a l'air correct.

[Doraki]

Le vrai problème c'est de montrer que l'ensemble des diviseurs communs à a et b a un élément maximum pour la relation divise.

[Judoboy]

Le vrai problème c'est de montrer que l'ensemble des diviseurs communs à a et b a un élément maximum pour la relation divise.

Certes, mais je ne suis pas sûr que ce soit l'objet de la question.

[savancosinus]

Le vrai problème c'est de montrer que l'ensemble des diviseurs communs à a et b a un élément maximum pour la relation divise.

Bon j'ai planché un peu dessus, mais j'y arrive pas :dodo:

Un coup de pouce ....? :hein:

[wserdx]

Il me semble que est l'élément maximal de au sens de la relation divise, (par définition!). Il suffit donc de montrer que avec au sens n°1.

[Doraki]

Bon j'ai planché un peu dessus, mais j'y arrive pas :dodo:

Un coup de pouce ....? :hein:

Tu as quoi à disposition ? en général, l'existence et les propriétés du pgcd sont le point de départ de toutes les propriétés arithmétiques de Z.
Il y a d'autres anneaux pour lesquels ce n'est plus vrai.

Soit c le plus petit élément strictement positif de aZ+bZ.
il existe u et v tels que c = au+bv, donc si d divise a et d divise b alors d divise c.
Si a = cq+r avec 0 <= r < c, alors r = a-cq = a(1-qu)+b(-qv) est dans aZ+bZ, donc r=0.
Donc a = cq : c divise a, et de même, c divise b.
Donc c est un diviseur commun à a et à b, et comme tous les diviseurs commun à a et à b divisent c, c'est dont un élément maximum.

[savancosinus]

Il me semble que est l'élément maximal de au sens de la relation divise, (par définition!). Il suffit donc de montrer que avec au sens n°1.

En fait j'aimerais montrer l'existence du PGCD de la définition 2 (relation "divise") sans utiliser la déf 1 (relation <=).

Sinon c'est bon il n'y a rien à faire (enfin je crois) :
Le PGCD définition 1 existe bien (plus grand élément dans un ensemble majoré de )
ET
On a l'équivalence des deux définitions.
DONC
La définition 2 existe elle aussi.

Tu as quoi à disposition ? en général, l'existence et les propriétés du pgcd sont le point de départ de toutes les propriétés arithmétiques de Z.
Il y a d'autres anneaux pour lesquels ce n'est plus vrai.
Soit c le plus petit élément strictement positif de aZ+bZ.
il existe u et v tels que c = au+bv, donc si d divise a et d divise b alors d divise c.
Si a = cq+r avec 0 <= r < c, alors r = a-cq = a(1-qu)+b(-qv) est dans aZ+bZ, donc r=0.
Donc a = cq : c divise a, et de même, c divise b.
Donc c est un diviseur commun à a et à b, et comme tous les diviseurs commun à a et à b divisent c, c'est dont un élément maximum.

Tu pars de c plus petit élément strict. positif de aZ+bZ (au sens )
Tu montres que c divise a et b et que tout diviseur de a et b divise c.
C'est ce que j'ai fait pour montrer l'équivalence des deux définitions (en fait c'est Bezout) mais je me dis qu'on doit pouvoir montrer l'existence du pgcd dans la définition 2 sans passer par ça ...? En utilisant des outils ensemblistes ou algébriques élémentaires (comme pour l'existence du pgcd dans la définition 1).

J'ai commencé un truc ...
Notons
On veut montrer l'existence de :


Lorsque il n'y a rien à montrer.
Supposons
On veut montrer que
Supposons l'inverse :

J'arrive à montrer une absurdité lorsque donc OK
Mais je n'arrive pas à généraliser #D = 3 etc ... Donc c'est peut être pas la bonne voie ... :dodo:

Bonne nuit.

[Doraki]

mais je me dis qu'on doit pouvoir montrer l'existence du pgcd dans la définition 2 sans passer par ça ...? En utilisant des outils ensemblistes ou algébriques élémentaires (comme pour l'existence du pgcd dans la définition 1).

Pas que je sache.

[wserdx]

Je ne sais pas si c'est ce que tu cherches, mais ça peut t'ouvrir des pistes.
Si tu considères la suite des nombres premiers, tu peux envoyer les éléments de sur les suites à valeurs dans et à support fini (c'est-à-dire dont le nombre de valeurs non nulles est fini), par la relation . Je ne sais pas s'il existe une notation consacrée, appelons , l'ensemble de ces suites.
Tu as alors où la relation est définie par
La relation (divise) comme la relation sont évidemment des relations d'ordre partiel. Le pgcd dans devient alors le min dans avec
Il te reste à montrer que

[Judoboy]

Je suis pas sûr de comprendre ce que tu écris wserdx, mais effectivement en utilisant le théorème fondamental de l'arithmétique c'est assez immédiat puisqu'on construit directement le pgcd(a,b), qui va satisfaire aux 2 définitions.