Arithmétique pgcd et ppcm
-
Ggalois dernière édition par
Salut et merci d'avance pour votre aide
Montrerque PGCD(a+b; ppcm(a;b))=PGCD(a;b)
J'ai posé d et d' ces deux pgcd et j'ai essayé de prouver que chacun d'eux divise l'autre mais j'ai pas arrivé
-
@galois Bonsoir,
Utilise la relation : (PPMC(a,b)=a⋅bPGCD(a,b))( \text{PPMC}(a, b) = \dfrac{a \cdot b}{\text{PGCD}(a, b)} )(PPMC(a,b)=PGCD(a,b)a⋅b).
d=PGCD(a,b)d = \text{PGCD}(a, b)d=PGCD(a,b), alors on peut écrire a=d⋅ma = d \cdot ma=d⋅m et b=d⋅nb = d \cdot nb=d⋅n pour certains entiers mmm et nnn qui sont premiers entre eux (c'est-à-dire PGCD(m,n)=1\text{PGCD}(m, n) = 1 PGCD(m,n)=1).a+b=d⋅m+d⋅n=d(m+n)a + b = d \cdot m + d \cdot n = d(m + n)a+b=d⋅m+d⋅n=d(m+n)
PPMC(a,b)=a⋅bPGCD(a,b)=(d⋅m)(d⋅n)d=d⋅m⋅n\text{PPMC}(a, b) = \dfrac{a \cdot b}{\text{PGCD}(a, b)} = \frac{(d \cdot m)(d \cdot n)}{d} = d \cdot m \cdot nPPMC(a,b)=PGCD(a,b)a⋅b=d(d⋅m)(d⋅n)=d⋅m⋅n
a+b=d(m+n)a + b = d(m+n)a+b=d(m+n) et PPMC(a,b)=d⋅m⋅n\text{PPMC}(a, b) = d \cdot m \cdot nPPMC(a,b)=d⋅m⋅n.
Donc, PGCD(a+b,PPMC(a,b))=PGCD(d(m+n),d⋅m⋅n))\text{PGCD}(a+b, \text{PPMC}(a, b)) = \text{PGCD}(d(m+n), d \cdot m \cdot n))PGCD(a+b,PPMC(a,b))=PGCD(d(m+n),d⋅m⋅n)).PGCD(d(m+n),d⋅m⋅n))=d⋅PGCD(m+n,m⋅n)\text{PGCD}(d(m+n), d \cdot m \cdot n)) = d \cdot \text{PGCD}(m+n, m \cdot n)PGCD(d(m+n),d⋅m⋅n))=d⋅PGCD(m+n,m⋅n)
Puisque mmm et nnn sont premiers entre eux, on peut montrer que PGCD(m+n,m⋅n)=1\text{PGCD}(m+n, m \cdot n) = 1 PGCD(m+n,m⋅n)=1. En effet, tout diviseur commun de (m+n)( m+n )(m+n) et (m⋅n( m \cdot n (m⋅n) doit diviser aussi (m+n−m⋅n)( m+n - m \cdot n )(m+n−m⋅n) et ainsi de suite, ce qui montre que le seul diviseur commun est 1.
Donc PGCD(a+b,PPMC(a,b))=d⋅1=d=PGCD(a,b)\text{PGCD}(a+b, \text{PPMC}(a, b)) = d \cdot 1 = d = \text{PGCD}(a, b)PGCD(a+b,PPMC(a,b))=d⋅1=d=PGCD(a,b)
-
Ggalois dernière édition par
@Noemi merci beaucoup mais la différence faite à la fin ne donne ni m ni n
-
Pour la démonstration du PGCD\text{PGCD}PGCD de m+nm+nm+n et m.nm.nm.n
Supposons qu'il existe un entier ddd tel que ddd divise à la fois m+nm+nm+n et m⋅nm \cdot nm⋅n. Cela signifie que :
d∣(m+n)etd∣(m⋅n)d \mid (m+n) \quad \text{et} \quad d \mid (m \cdot n)d∣(m+n)etd∣(m⋅n).
Sachant que mmm et nnn sont premiers entre eux.
Si ddd divise mmm, alors m=kdm = kdm=kd pour un certain entier kkk.
En utilisant d∣(m+n)d \mid (m+n)d∣(m+n), nous avons :d∣(kd+n) ⟹ d∣nd \mid (kd + n) \implies d \mid nd∣(kd+n)⟹d∣n.
Cela signifie que ddd divise nnn également, ce qui contredit le fait que mmm et nnn sont premiers entre eux.Même démarche pour si ddd divise nnn.
Comme ddd ne peut pas diviser mmm ni nnn, cela implique que le seul diviseur commun possible de m+nm+nm+n et m⋅nm \cdot nm⋅n est 1. Par conséquent, nous avons :
PGCD(m+n,m⋅n)=1\text{PGCD}(m+n, m \cdot n) = 1PGCD(m+n,m⋅n)=1.
-
Ggalois dernière édition par
@Noemi merci beaucoup c'est claire maintenant