pgcd(ka,kb) = k pgcd(a,b)

pGoron

Bonjour tout le monde

   Je me demandais s'il était possible de montrer que $pgcd(ka,kb) = k \times pgcd(a,b)$ sans passer par l'algorithme d'Euclide (avec $k\, pgcd(a,b) = k\, pgcd(b,r) = \ldots = k \, r_n = pgcd(ka,kb)$) ni bien sûr l'identité de Bézout.

   Désolé si cette question est triviale ou si elle a déjà obtenu une réponse (que je ne trouve pas)... !

Rémy

[EDIT] Les termes de ma question n'étaient pas clairement définis :

• pas de décomposition en produit de facteurs premiers ;
•  et le pgcd est défini de manière "naïve", au sens de l'ordre usuel sur $\mathbb N$ et pas de la divisibilité.

Rescassol

Bonjour
En partant de $a=da'$ et $b=db'$ avec $a'\wedge b'=1$.
Cordialement,
Rescassol

nicolas.patrois

Par la décomposition en facteurs premiers ?

Foys

Pour tous entiers $a,b,c\geq 1$, $c$ divise $a$ et $b$ si et seulement si $c$ divise $a$ et $c$ divise $b$. D'autre part du fait de l'intégrité de $\Z$, pour tous entiers $p,q,r\geq 1$, $p$ divise $q$ si et seulement si $pr$ divise $qr$. Avec ces ingrédients on s'en sort.

gai requin

Aves les idéaux de $\Z$,$$<(ka)\wedge(kb)>=<ka,kb>=k<a,b>=k<a\wedge b>=<k(a\wedge b)>$$ donc $(ka)\wedge(kb)=\pm k(a\wedge b)$.

pGoron

Bonjour et merci pour vos réponses.

   Je n'avais pas très bien défini les termes de ma question : je veux éviter la décomposition en produits de nombres premiers.

   Et surtout, le pgcd est défini avec l'ordre usuel sur $\mathbb N$, pas au sens de la divisibilité. Et donc je n'obtiens que : $k \, pgcd(a,b) \leqslant pgcd(ka, kb)$.

   Il faut bien utiliser un axiome de $\mathbb N$ et/ou la division euclidienne pour montrer l'autre inégalité, non ?

   Même l'emploi de $a'$ et $b'$ premiers entre eux ne résout pas ce souci...

pGoron

   Je suppose qu'il est indispensable de montrer d'abord que tout diviseur commun divise le pgcd...

   Finalement, Daniel Perrin propose quelque chose là-dessus ici : https://www.imo.universite-paris-saclay.fr/~perrin/CAPES/arithmetique/Surlepgcd.pdf. Et Wikipedia en parle également : https://fr.wikipedia.org/wiki/Plus_grand_commun_diviseur_de_nombres_entiers#Tout_diviseur_commun_divise_le_PGCD

   S'il existe $a,b \in \mathbb N$ dont des diviseurs ne divisent pas le pgcd, alors l'ensemble des sommes $a+b$ des tels $(a,b)$ admet un minimum. Ce qui est contredit par le fait que $(b-a,a)$vérifie aussi cette qualité, et qu'il est inférieur au minimum.

   Je suis bien obligé d'utiliser un truc "à la Euclide"...

OShine

Utilise la définition du PGCD. 

pGoron

OShine

Avec la définition naïve du pgcd, c'est possible de montrer l'égalité $pgcd(ka,kb) = k\, pgcd(a,b)$ ?

[Inutile de reproduire le message précédent. AD]

Area 51

En invoquant $\forall x,y \in \mathbb{Z}, \; (x \wedge y) (x \vee y) = xy$ et le fait que $kx \vee ky = k (x \vee y)$, on en déduit que $kx \wedge ky = k (x \wedge y)$.

OShine

PGoron je vais essayer. 

gai requin

A-t-on le droit de faire une preuve par récurrence ?

noix de totos

Soient $d = (a,b)$ et $D:=(ka,kb)$. On pose aussi $a=d a_1$ et $b=d_1$ avec $(a_1,b_1)=1$. D'après Bézout, il existe $u,v \in \mathbb{Z}$ tels que $a_1u+b_1v=1$. Puisque $D \mid ka$ et $D \mid kb$, $D \mid (kda_1u+kdb_1v) = kd$. La réciproque $kd \mid D $ est facile.

gai requin

Sans Bézout noix de totos

pGoron

Area 51 a dit :

En invoquant $\forall x,y \in \mathbb{Z}, \; (x \wedge y) (x \vee y) = xy$ et le fait que $kx \vee ky = k (x \vee y)$, on en déduit que $kx \wedge ky = k (x \wedge y)$.

Tu as raison... Mais je ne voulais pas non plus par le ppcm : sinon il faut aussi démontrer que $(x \wedge y) (x \vee y) = xy$ !

gai requin a dit :

A-t-on le droit de faire une preuve par récurrence ?

C'est ce que Wikipedia propose (genre de raisonnement inverse de Perrin). Personnellement j'aime bien l'idée du contre-exemple minimal impossible.

OShine

J'utilise le théorème suivant vu en MPSI : 

Soit $a$ et $b$ deux entiers naturels tous les deux non nuls et $d$ leur PGCD. Alors $\boxed{\forall n \in \N \  (n \mid a \ \ \text{et} \ n \mid b) \Leftrightarrow n \mid d}$

Le PGCD de $a$ et $b$ est le seul élément $d \in \N^{*}$ à vérifier l'équivalence.

=> Soit $n \mid ka$ et $n \mid kb$. Montrons que $n \mid k PGCD(a,b)$.

Or $a \mid PGCD(a,b)$ et $b \mid PGCD(a,b)$ par transitivité et produit on a $n \mid kPGCD(a,b)$.

<= Supposons que $n \mid k PGCD(a,b)$. Montrons que $n \mid ka$ et $n \mid kb$.

Il existe des entiers $a'$ et $b'$ premiers entre eux tels que $a= PGCD(a,b) a'$ et $b=PGCD(a,b) b'$

Donc $ka = kPGCD(a,b) a'$ mais $n \mid k PGCD(a,b)$ donc $n \mid ka$. De même on montre que $n \mid kb$.

Conclusion : par caractérisation du PGCD on a montré que $\boxed{PGCD(ka,kb)=k PGCD(a,b)}$

df

Si on utilise la décomposition en facteurs premiers de $a$ et $b$, on a $d=pgcd(a,b)=\prod_{i=1}^{\mathscr{l}}p_i^{\gamma_i}$ avec $\gamma_i=\min(\alpha_i, \beta_i)$.
Les facteurs premiers de $k$, pour passer de $a$ et $b$ à $ka$ et $kb$, s’ajoutent de la même manière dans les décompositions de $a$, $b$ et $d$ (i.e. on ajoute toujours les mêmes valeurs constantes à chacun des exposants figurant dans les décompositions en facteurs premiers de $a$, $b$ et $d$).

noix de totos

Gai Requin : oui, je n'ai pas lu le premier message...Du coup, je ne vois pas l'intérêt de ce fil !

raoul.S

OShine a dit : 

Or $a \mid PGCD(a,b)$ et $b \mid PGCD(a,b)$...

🥶

gai requin

$\renewcommand{\gcd}{\,\mathrm{pgcd}}$Montrons par récurrence sur $k\geq 1$ que pour tous $a\geq 1$, $b\geq 1$, $\gcd(ka,kb)=k\gcd(a,b)$.
C'est clair pour $k=1$.

Soit $k\geq 2$ tel que, pour tout $1\leq m\leq k-1$, on a $\gcd(ma,mb)=m\gcd(a,b)$ pour tous $a\geq 1$ et $b\geq 1$.
Fixons $a\geq 1$ et $b\geq 1$.
Soit alors $q,r\in\N$ tels que $\gcd(ka,kb)=kq+r$ avec $0\leq r<k$.
Il existe $d\geq 1$ et $d'\geq 1$ tels que $ka=d(kq+r)$ et $kb=d'(kq+r)$.
Il est clair que $d$ et $d'$ sont premiers entre eux.
De plus, $k$ divise $dr$ et $d'r$ donc, si $r\neq 0$, il vient $k\leq\gcd(dr,d'r)=r\gcd(d,d')=r$ : contradiction.
Donc $r=0$ et $k$ divise $\gcd(ka,kb)$.
Or, $\gcd(ka,kb)/k$ divise $a$ et $b$ facilement donc $\gcd(ka,kb)\leq k\gcd(a,b)$...

OShine

@raoul.S merci je me suis emballé.

pGoron

gai requin a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2348653/#Comment_2348653

[Inutile de recopier l'avant-dernier message. Un lien suffit. AD]

Sympa ça ! Merci d'avoir pris le temps.

noix de totos a dit :

Gai Requin : oui, je n'ai pas lu le premier message...Du coup, je ne vois pas l'intérêt de ce fil !

Sans doute que je n'ai pas clairement dit ce que je voulais au début : démontrer cette propriété avec... rien : ni l'algorithme d'Euclide, ni Bézout ; seulement la définition du pgcd.

Parce que je trouve dommage dans un cours de voir cette propriété du pgcd n'apparaître qu'après l'algorithme d'Euclide, ou Bézout (comme une conséquence). Pareil pour $d\mid a \mbox{ et } d\mid b \Leftrightarrow d \mid \gcd(a,b)$.

raoul.S

Comme le montre df, dans un anneau factoriel la propriété est encore vraie. Dans des anneaux plus généraux Wikipedia dit que la propriété est vraie dans le sens suivant : dans un anneau intègre quelconque si PGCD(ac, bc) existe alors PGCD(a, b) existe et $\gcd(ac,bc)=c\gcd(a,b)$ à un inversible près. Je ne sais pas si la preuve est facile...

gai requin

$c$ divise $\gcd(ca,cb)$ et si $d$ divise $a$ et $b$, alors $cd$ divise $\gcd(ca,cb)$ donc $d$ divise $\gcd(ca,cb)/c$...

raoul.S

Oui finalement c'est facile. @gai requin tu as montré que si $\gcd(ac,bc)$ existe alors $\gcd(a,b)$ existe, il reste juste à montrer que $\gcd(ac,bc)/c$ est un diviseur commun de $a$ et $b$.

On a $\gcd(ac,bc)\mid ac$ donc $\gcd(ac,bc)/c \mid a$. De même, $\gcd(ac,bc)/c \mid b$. Donc  $\gcd(a,b)$ existe et est égal à $\gcd(ca,cb)/c$.

gai requin

Et si $\gcd(a,b)$ existe, est-ce que $\gcd(ca,cb)$ existe pour tout $c$ ?

OShine

Raoul.S on peut le démonter avec la propriété que j'ai donnée ? 

raoul.S

@OShine la propriété que tu as donnée est la définition d'un pgcd dans un anneau général. Donc oui, d'ailleurs la preuve ci-dessus utilise cette définition.

@gai requin non

GG

pGoron, la "bonne" définition du pgcd est évidemment le plus grand diviseur commun au sens de la divisibilité, l'inf donc.
Dans ce cas, le plus simple est de faire comme suggéré par Rescassol.
Je note $(a, b)$ le pgcd de $a$ et $b$.
Lemme : On suppose $a = da'$ et $b = db'$. Alors $ d = (a, b) \Leftrightarrow (a', b') = 1$.
Supposons $d = (a, b)$ et soit $k$ un diviseur commun de $a'$ et $b'$.
$a = dka''$, $b = dkb''$
$ dk \mid d$,
$k = 1$ et $(a', b') = 1$.
Réciproquement, supposons $(a', b') = 1$ et soit $D = (a, b)$.
$a = Da''$, $b = Db''$
$D = dq$
$dqa'' = da'$, $dqb'' =db'$
$q \mid a', b'$
$q = 1, d = D$
$\square$

Maintenant on a $a = (a, b)a'$, $b = (a, b)b'$, donc ($a', b') = 1$.
$ka = k(a, b)a'$, $kb = k(a, b)b'$, donc $(ka, kb) = k(a, b)$.

Si tu tiens absolument à ta définition, il te reste à montrer que tout diviseur de $a$ et $b$ divise le plus grand pour l'ordre naturel !

gai requin

@raoul.S : Tu peux trouver un contre-exemple dans $\Z[t^2,t^3]$

Rescassol

Bonjour,

Merci GG, il y a quand même quelqu'un qui revient aux fondamentaux.

Cordialement,
Rescassol

GG

Salut Rescassol !

raoul.S

@gai requin Tu peux trouver un contre-exemple dans $\Z[i\sqrt{5}]$

PS1. pour $\Z[t^2,t^3]$ on a $\gcd(t^2,t^3)=1$ mais $\gcd(t^3\cdot t^2, t^3\cdot t^3)$ n'existe pas. En effet $t^2$ et $t^3$ sont des diviseurs communs mais aucun multiple commun de $t^2$ et $t^3$ ne divise $t^5$ et $t^6$.

PS2. GG GG (seuls les gameurs comprendront...)