Application au calcul de pgcd - Bibm@th.net
Exercice 1 - Application au calcul de pgcd [Ajouter à ma feuille d'exos] [Signaler une erreur] [Copier le lien]
Enoncé 
Soient $a,b,c\in\mathbb N^*$ et soit $n\in\mathbb N^*$.
- Démontrer que $c|ab\implies c|(a\wedge c)(b\wedge c)$.
- Démontrer que $(a\wedge b)^n=a^n \wedge b^n$.
- (Plus difficile) Calculer $(a^2+ab+b^2)\wedge ab$.
Indication 
A chaque fois, on utilisera une décomposition en facteurs premiers des entiers concernés, et la caractérisation du pgcd à l'aide de cette décomposition.
Corrigé
- On décompose $a,$ $b$ et $c$ en produit de facteurs premiers : $$a=p_1^{\alpha_1}\dots p_r^{\alpha_r},\ b=p_1^{\beta_1}\dots p_r^{\beta_r},\ c=p_1^{\gamma_1}\dots p_r^{\gamma_r}$$ (on autorise que les $\alpha_i,$ les $\beta_i$ et les $\gamma_i$ sont nuls car $a,$ $b$ et $c$ n'ont pas forcément les mêmes facteurs premiers). La condition $c|ab$ signifie que $\gamma_j\leq \alpha_j+\beta_j$ pour tout $j$. De plus, on a $$a\wedge c=p_1^{\min(\alpha_1,\gamma_1)}\dots p_r^{\min(\alpha_r,\gamma_r)}$$ $$b\wedge c=p_1^{\min(\beta_1,\gamma_1)}\dots p_r^{\min(\beta_r,\gamma_r)}$$ et donc on a $c|(a\wedge c)(b\wedge c)$ si et seulement si, pour tout $j$ de $1,\dots,r$, on a $$\gamma_j\leq \min(\alpha_j,\gamma_j)+\min(\beta_j,\gamma_j).$$ Mais si $\min(\alpha_j,\gamma_j)=\gamma_j$ ou $\min(\beta_j,\gamma_j)=\gamma_j$, c'est trivial. Sinon on a $$\min(\alpha_j,\gamma_j)+\min(\beta_j,\gamma_j)=\alpha_j+\beta_j\geq\gamma_j$$ par hypothèse. Ceci prouve le résultat.
- Écrivons à nouveau $$a=p_1^{\alpha_1}\dots p_r^{\alpha_r},\ b=p_1^{\beta_1}\dots p_r^{\beta_r}$$ et posons $\gamma_j=\min(\alpha_j,\beta_j)$. Alors $$a\wedge b=p_1^{\gamma_1}\dots p_r^{\gamma_r}\implies (a\wedge b)^n=p_1^{n\gamma_1}\dots p_r^{n\gamma_r}.$$ De même, $$a^n=p_1^{n\alpha_1}\dots p_r^{n\alpha_r},\ b^n=p_1^{n\beta_1}\dots p_r^{n\beta_r}$$ de sorte que $$a^n\wedge b^n=p_1^{\delta_1}\cdots p_r^{\delta_r}$$ avec $\delta_j=\min(n\alpha_j,n\beta_j)=n\min(\alpha_j,\beta_j)=n\gamma_j.$
- Soit $d=(a^2+ab+b^2)\wedge ab$. On peut commencer par remarquer que $d=(a^2+b^2)\wedge ab$. Décomposons $a$, $b$ et $d$ en produits de facteurs premiers : $$a=p_1^{\alpha_1}\dots p_r^{\alpha_r}, b=p_1^{\beta_1}\dots p_r^{\beta_r},\ d=p_1^{\gamma_1}\dots p_r^{\gamma_r}.$$ Puisque $d|ab$, on a $\gamma_j\leq \alpha_j+\beta_j$ pour tout $j$. Si $\alpha_j=\beta_j$, on en déduit que $\gamma_j\leq 2\min(\alpha_j,\beta_j)$. Si maintenant $\alpha_j\neq \beta_j$, on peut supposer $\alpha_j<\beta_j$, alors $$a^2+b^2=p_j^{2\alpha_j}(q+p_j^{2\beta_j-2\alpha_j}r)$$ avec $q\wedge p_j=1$. En particulier, $(q+p_j^{2\beta_j-2\alpha_j}r)\wedge p_j=1$, et donc $\gamma_j\leq 2\alpha_j=2\min(\alpha_j,\beta_j)$. Ceci démontre en particulier que $d|a^2\wedge b^2$. Réciproquement, on va prouver que $a^2\wedge b^2|ab$. Puisqu'il est clair qu'on a aussi $a^2\wedge b^2|a^2+b^2$, on pourra conclure que $d=a^2\wedge b^2.$ Mais $$ab=p_1^{\alpha_1+\beta_1}\dots p_r^{\alpha_r+\beta_r}\textrm{ et }a^2\wedge b^2=p_1^{\min(2\alpha_1,2\beta_1)}\dots p_r^{\min(2\alpha_r,2\beta_r)}$$ ce qui prouve ce que l'on voulait.