Arithmetiques Pgcd

par **Mouraddddd** » 15 Juil 2009, 19:56

bonjour, pourriez vous m'aider à résoudre cet exercice :
Soit 3 entiers non nuls a,b et c tels que a et c sont premiers entre eux.
1.Montrer que tout diviseur de a distinct de 1 est premier avec c.
2.Montrer que PGCD (a , b) divise PGCD (a , bc).
merci d'avance pour votre collaboration.

par **leon1789** » 15 Juil 2009, 20:06

Mouraddddd a écrit:bonjour, pourriez vous m'aider à résoudre cet exercice :
Soit 3 entiers non nuls a,b et c tels que a et c sont premiers entre eux.
1.Montrer que tout diviseur de a distinct de 1 est premier avec c.

pourquoi distinct de 1 ? hypothèse inutile :
--> tout diviseur de a est premier avec c !

Mouraddddd a écrit:2.Montrer que PGCD (a , b) divise PGCD (a , bc).
merci d'avance pour votre collaboration.

Quels sont tes outils en arithmétique ? définition du pgcd ? définition de diviseur ? définition de nombres premiers entre eux ? théorème de Bezout ?

par **Timothé Lefebvre** » 16 Juil 2009, 01:25

Bonjour,

ou en sont tes avancees ?

par **leon1789** » 16 Juil 2009, 09:13

Timothé Lefebvre a écrit:Bonjour,

ou en sont tes avancees ?

:hein: tu parles à qui ? Tu t'es trompé de discussion ? :ptdr:

par **egan** » 16 Juil 2009, 09:41

Ya un lien entre les deux questions ?
Il me semble que l'on peut faire la deuxième sans la première.

par **leon1789** » 16 Juil 2009, 09:49

egan a écrit:Il me semble que l'on peut faire la deuxième sans la première.

oui c'est vrai (ça peut se faire en trois lignes avec Bezout).

On peut même généraliser la seconde :
si pgcd(a,b,c) = 1 alors pgcd(a,bc) = pgcd(a,b).pgcd(a,c)

par **egan** » 16 Juil 2009, 09:55

Comment tu ferais ça avec Bezout ?
Tu arrives à ça pgcd(a,bc) = pgcd(a,b).pgcd(a,c) comment ? Ca parraît logique mais pour l'expliquer proprement j'ai du mal.

J'avais pensé comme ça moi:
PGCD(a,b) est un diviseur commun à a et a b donc PGCD(a,b) divise a.
De plus, il divise b donc il divise tout multiple de b donc il divise bc.
PGCD(a,b) est un diviseur commun à a et bc donc il est un diviseur de PGCD(a,bc).

par **egan** » 16 Juil 2009, 10:07

pgcd(a,bc) = pgcd(a,b).pgcd(a,c)

Par disjonction de cas, ça peut se faire.
Si PGCD(a,b,c)=1 soit a premier avec b, a premier avec c, b premier avec c ou a,b,c premiers entre eux.
Si a premier avec b, PGCD(a,bc)=PGCD(a,c)=PGCD(a,c)*1=PGCD(a,c)*PGCD(a,b)
De même, on traiterait le cas a premier avec c.
Si a,b,c premiers entre eux deux à deux:
PGCD(a,bc)=1=1*1=PGCD(a,b)*PGCD(a*c)

Reste le dernier cas...

par **egan** » 16 Juil 2009, 10:18

Ah ba si, c'est pas si dure que ça.
Si b et c sont premiers entre eux, alors leurs décompositions respectives en produits de facteurs premiers ne contiennent aucun facteur commun.
De ce fait, PGCD(a,bc) est égal au produit des facteurs communs aux décompositions de a et de bc, facteurs communs affectés bien entendu du plus petit exposant figurant dans l'une ou l'autre des décompositions.
En appliquant cette propriété à PGCD(a,b) et PGCD(a,c), il en découle que PGCD(a,bc)=PGCD(a,b)*PGCD(a,c).

PS: désolé pour ces affreuses explications en français qui ne sont jamais très limpides..., lol.
Leon1789, ta démonstration avec Bezout m'interresse toujours. ^^

par **leon1789** » 16 Juil 2009, 11:38

a et c sont premiers entre eux. Montrer que PGCD (a , b) divise PGCD (a , bc).

leon1789 a écrit:ca peut se faire en trois lignes avec Bezout

Ah, je me suis trompé : j'avais trop rapidement lu PGCD (a , bc) divise PGCD (a , b)...

Démonter PGCD (a , b) divise PGCD (a , bc) est instantané ! Un diviseur commun de a et b est un diviseur commun de a et bc (comme disait egan). Il n'y a même pas besoin d'hypothèse sur a et c !! :hum:

Je pense que Mouraddddd s'est trompé dans son énoncé : c'est bien PGCD(a,bc) divise PGCD(a,b) qu'il faut démontrer sous hypothèse a et c premiers entre eux. Pour cela, Bezout est intéressant : 1 = PGCD(a,c)=ua+vc que l'on multiplie par b, d'où b = ub(a)+v(bc). Or PGCD(a,bc) divise a et bc donc divise b, donc divise PGCD(a,b).

leon1789 a écrit:On peut même généraliser la seconde :
si pgcd(a,b,c) = 1 alors pgcd(a,bc) = pgcd(a,b).pgcd(a,c)

egan a écrit:- Si a premier avec b (...)
- De même, on traiterait le cas a premier avec c.
- Si b et c sont premiers entre eux (...)
- Si a,b,c premiers entre eux deux à deux (...) étrange ce cas

Cela ne convient pas : pgcd(a,b,c) = 1 est une hypothèse bien moins forte que les quatre cas que tu as considérés. Par exemple avec a=6, b=10, c=15, on a bien PGCD(a,b,c)=1, mais aucun de tes quatre cas ne sont vérifiés.

par **egan** » 16 Juil 2009, 12:13

Ah oui en effet, ça marche pas. Erreur de raisonnement de ma part, j'ai cru que la transitivité s'appliquait sur les nombres premiers entre eux...
Comment tu montres ça alors ?
si pgcd(a,b,c) = 1 alors pgcd(a,bc) = pgcd(a,b).pgcd(a,c)

D'ailleurs, quels que soient a,b,c PGCD(a,b) divise PGCD(a,bc). Or si a et c sont premiers entre eux, alors PGCD(a,bc) divise PGCD(a,b).
Donc si a et c sont premiers entre eux, alors PGCD(a,b)=PGCD(a,bc).

Pour le cas, a,b,c sont premiers deux à deux, tu aurais a=5,b=7,c=12 par exemple. Pourquoi cela est-il étrange ?
Reste le cas où PGCD(a,b,c)=1 sans aucune hypothèse sur a,b,c, soit, tout ce que j'ai écrit ne sert à rien, lol.

par **leon1789** » 16 Juil 2009, 13:19

egan a écrit:- Si a premier avec b (...)
- De même, on traiterait le cas a premier avec c.
- Si b et c sont premiers entre eux (...)
- Si a,b,c premiers entre eux deux à deux (...) étrange ce cas

egan a écrit:Pour le cas, a,b,c sont premiers deux à deux, tu aurais a=5,b=7,c=12 par exemple. Pourquoi cela est-il étrange ?

Je disais étrange car c'est un sous-cas des trois cas précédents à la fois : quand a,b,c premiers entre eux deux à deux alors pgcd(a,b)=1 et pgcd(a,c)=1 et pgcd(b,c)=1... Donc il y a trois raisons pour lequel ne pas traiter ce cas :zen:

egan a écrit:quels que soient a,b,c PGCD(a,b) divise PGCD(a,bc). Or si a et c sont premiers entre eux, alors PGCD(a,bc) divise PGCD(a,b).
Donc si a et c sont premiers entre eux, alors PGCD(a,b)=PGCD(a,bc).

exact. Et on voit sans problème que ce résultat est un cas particulier du suivant.

egan a écrit:Comment tu montres ça alors ?
si pgcd(a,b,c) = 1 alors pgcd(a,bc) = pgcd(a,b).pgcd(a,c)

En fait, il y a encore mieux !
Quels que soient

, on a

(avec un pgcd dans un pgcd... ça se complique :id: )

egan, tu es à quel niveau d'étude ? (pour ne pas donner une preuve trop complexe)

par **egan** » 16 Juil 2009, 13:29

Je passe en MPSI à la rentrée.

par **leon1789** » 16 Juil 2009, 14:06

egan a écrit:Je passe en MPSI à la rentrée.

ah.

Bon je donne pour l'instant une preuve abstraite : elle est tellement rapide et pure que je ne peux pas m'en priver !

ce qui montre de suite

.

Je vais réfléchir pour egan.

par **leon1789** » 16 Juil 2009, 15:17

leon1789 a écrit:Je vais réfléchir pour egan.

on va se contenter de
pgcd(a,b,c)=1 implique

!

Première partie :
montrons que

divise

Soit e=pgcd(a,b) et f=pgcd(a,c)
e divise b et f divise c donc e.f divise b.c (*)

On écrit 1 = pgcd(a,b,c) = a.u + b.v + c.w (Bezout, c'est du lourd ! :id: )
d'où a = a.a.u + a.b.v + a.c.w
Or e et f divisent a donc e.f divise a.a (1)
e divise b et f divise a donc e.f divise a.b (2)
e divise a et f divise c donc e.f divise a.c (3)
(1) et (2) et (3) donnent e.f divise a.a.u + a.b.v + a.c.w = a (**)

(*) et (**) donnent e.f divise pgcd(bc, a)

Seconde partie :
montrons que

est multiple de

...

par **leon1789** » 16 Juil 2009, 16:04

egan, ça te va ?

par **egan** » 16 Juil 2009, 16:12

C'est tout simplement brillantissime !

par **egan** » 18 Juil 2009, 14:43

Comme tu l'as dit leon,
PGCD(PGCD(a;b);PGCD(c;d))=PGCD(a;b;c;d).

Normalement (corrigez moi si je dis une bêtise), on a aussi ça:
PPCM(PPCM(a;b);PPCM(c;d))=PPCM(a;b;c;d)
Donc de ce fait, de la même manière que précédemment, on aurait:
PPCM(a;b).PPCM(a;c)=PPCM(aPPCM(a;b;c);bc)

D'ailleurs, ya ça aussi:

PGCD(ka;kb;kc)=kPGCD(a;b;c), ça marche pour n entiers et avec le PPCM.
Si PGCD(a;b;c)=D, alors a=Da', b=Db', c=Dc' avec PGCD(a';b';c')=1. (ça marche pour n entiers)
Par contre PGCD(a;b).PPCM(a;b)=ab, n'est vraie que pour deux entiers.

par **leon1789** » 18 Juil 2009, 15:27

egan a écrit:Normalement (corrigez moi si je dis une bêtise), on a aussi ça:
PPCM(PPCM(a;b);PPCM(c;d))=PPCM(a;b;c;d)

c'est exact

egan a écrit:Donc de ce fait, de la même manière que précédemment, on aurait:
PPCM(a;b).PPCM(a;c)=PPCM(aPPCM(a;b;c);bc)

exact aussi.

egan a écrit:D'ailleurs, ya ça aussi:

tout à fait

egan a écrit:PGCD(ka;kb;kc)=kPGCD(a;b;c), ça marche pour n entiers et avec le PPCM.

bien sûr

egan a écrit:Si PGCD(a;b;c)=D, alors a=Da', b=Db', c=Dc' avec PGCD(a';b';c')=1. (ça marche pour n entiers)

oui

egan a écrit:Par contre PGCD(a;b).PPCM(a;b)=ab, n'est vraie que pour deux entiers.

exact.

par **Karim35** » 21 Déc 2019, 04:05

leon1789 a écrit:

egan, ça te va ?

Bonjour
Je relance le sujet de plus de 10 ans !!!!

je pense qu'il suffit d'avoir b∧c=1 et ça marche , en effet
(a∧b)(a∧c)
=[(a∧b)a] ∧ [(a∧b)c]
=(a^2∧ab) ∧ (ac∧bc)
=a^2 ∧ ab ∧ ac ∧ bc (pas de souci, associativité du PGCD)
= a^2 ∧ a(b∧c) ∧ bc
= a^2 ∧ a ∧ bc (car b∧c=1)
= a(a∧1) ∧ bc
= a ∧ bc (car a∧1=1)

et voilà , quelqu'un peut confirmer, merci

Arithmetiques Pgcd

Arithmetiques Pgcd

Re:

Qui est en ligne