Exercices de PGCD et nombres premiers, Terminale

1. $\mathrm{pgcd}(\alpha ,\beta )=1$ :

Soit $k=\mathrm{pgcd}(\alpha ,\beta )$. Alors $k\mid \alpha$ et $k\mid \beta$, donc $kd\mid d\alpha =a$ et $kd\mid d\beta =b$. Ainsi $kd$ est un diviseur commun de $a$ et $b$. Or $d=\mathrm{pgcd}(a,b)$, donc $kd\le d$, soit $k\le 1$. Comme $k\ge 1$, on conclut $k=1$.

2. Calcul de $\mathrm{pgcd}(a+b,ab)$ :

$a+b=d\alpha +d\beta =d(\alpha +\beta )$ et $ab=d\alpha \cdot d\beta =d^2\alpha \beta$.

Soit $D=\mathrm{pgcd}(a+b,ab)=\mathrm{pgcd}(d(\alpha +\beta ),d^2\alpha \beta )$.

On factorise par $d$ : $D=d\mathrm{pgcd}(\alpha +\beta ,d\alpha \beta )$.

Puisque $\mathrm{pgcd}(\alpha ,\beta )=1$, on a $\mathrm{pgcd}(\alpha +\beta ,\alpha )=\mathrm{pgcd}(\beta ,\alpha )=1$ et $\mathrm{pgcd}(\alpha +\beta ,\beta )=\mathrm{pgcd}(\alpha ,\beta )=1$, donc $\mathrm{pgcd}(\alpha +\beta ,\alpha \beta )=1$.

Montrons que $\mathrm{pgcd}(\alpha +\beta ,d\alpha \beta )=\mathrm{pgcd}(\alpha +\beta ,d)$. Tout diviseur commun de $\alpha +\beta$ et $d$ divise aussi $d\alpha \beta$ : c'est un diviseur commun de $\alpha +\beta$ et $d\alpha \beta$, donc il divise $\delta =\mathrm{pgcd}(\alpha +\beta ,d\alpha \beta )$ ; en particulier $\mathrm{pgcd}(\alpha +\beta ,d)$ divise $\delta$. Réciproquement, tout diviseur commun de $\delta$ et $\alpha \beta$ divise $\alpha +\beta$ et $\alpha \beta$, donc divise $1$ : $\delta$ est premier avec $\alpha \beta$. Comme $\delta$ divise $d\alpha \beta$, le théorème de Gauss donne : $\delta$ divise $d$, donc $\delta$ divise $\mathrm{pgcd}(\alpha +\beta ,d)$. Ces deux entiers naturels non nuls se divisent mutuellement, ils sont égaux : $D=d\mathrm{pgcd}(\alpha +\beta ,d)$.

Conclusion : $\mathrm{pgcd}(a+b,ab)=d\mathrm{pgcd}(\alpha +\beta ,d)$.

3. Application : $35=30+5$ et $150=30\times 5$. Avec $a=30$ et $b=5$, on a $d=5$, $\alpha =6$ et $\beta =1$, et la question 2 donne $\mathrm{pgcd}(35,150)=5\mathrm{pgcd}(7,5)=5\times 1=5$.

Vérification par l'algorithme d'Euclide : $150=4\times 35+10$, $35=3\times 10+5$, $10=2\times 5+0$.

Donc $\mathrm{pgcd}(35,150)=5$.