$\text{PGCD}$

Soient $a$ et $b$ deux entiers relatifs non simultanément nuls.
On a $\text{PGCD}(a;b)=\text{PGCD}(|a|;|b|)$ et, pour tout couple $(a;b)\in {\mathbb{N}}^2$ avec $a\ne 0$ :
1. $\mathrm{PGCD}(a;b)⩾1$ ; $\mathrm{PGCD}(0;a)=a$ ; $\mathrm{PGCD}(1;a)=1$ ;
2. $a$ divise $b$ si, et seulement si, $\text{PGCD}(a;b)=a$;
3. $\text{PGCD}(a;b)=\text{PGCD}(a-b;b)$ (Méthode de la soustraction).

Voir exercice

67

p. 134.

Les diviseurs positifs de $700$ sont les suivants.


Si $\text{PGCD}(n;700)=25$, alors $25$ divise $n$. Donc $n$ est un multiple de $25$. Les multiples de $25$ inférieurs à $700$ sont les suivants.


Or $n$ ne peut pas être un multiple de $50,100,175$ ou $350$ car on aurait alors $\text{PGCD}(n;700)⩾50$.
L'ensemble cherché est donc $\{25;75;125;225;275;325;375;425;475;575;625;675\}$.

Exercices

28

et

29

p. 132.

Si $b$ divise $a$, alors $\text{PGCD}(a;b)=b$.
Sinon, on effectue la division euclidienne de $a$ par $b$.
Tant que le reste $r$ est non nul, on remplace $(a;b)$ par $(b;r)$ et on recommence. $\text{PGCD}(a;b)$ est le dernier reste non nul.

$450=198\times 2+54$
$198=54\times 3+36$
$54=36\times 1+18$
$36=18\times 2+0$

Le dernier reste non nul obtenu en appliquant l'algorithme d'Euclide vaut $18$ donc on en déduit que $\text{PGCD}(450;198)=18$.

Exercices

37

et

38

p. 132.

Voir exercice

75

p. 135.

Soit $(a;b)\in {\mathbb{Z}}^2$. On suppose que $a$ et $b$ ne sont pas simultanément nuls et on note $d\in \mathbb{Z}$ un diviseur commun à $a$ et $b$.
Montrons que $d$ divise $\text{PGCD}(a;b)$. Pour cela, montrons par récurrence que $d$ divise tous les restes de la suite construite par l'algorithme d'Euclide.

Initialisation : soient respectivement $q$ et $r_0$ le quotient et le reste de la division euclidienne de $a$ par $b$.
Alors $r_0=a-bq$ donc $d$ divise $r_0$ comme combinaison linéaire de $a$ et $b$.

Hérédité : on suppose qu'on a construit la suite $r_0,r_1,\dots ,r_m$ telle que, pour tout $k\in \{1;\dots ;m-1\},r_{k+1}$ soit le reste de la division euclidienne de $r_{k-1}$ par $r_k$ dont on note $q_k$ le quotient et qu'on a montré que $r_m$ et $r_{m-1}$ sont divisibles par $d$.
Alors $r_{m-1}=q_m{r}_m+r_{m+1}$ donc $r_{m+1}=r_{m-1}-r_m{q}_m$ est encore divisible par $d$.

Conclusion : par récurrence, on déduit que, pour tout $k\in \{1;\dots ;m\},r_k$ est divisible par $d$. Comme $\text{PGCD}(a;b)$ est le dernier terme non nul de cette suite, $\text{PGCD}(a;b)$ est divisible par $d$.
Réciproquement, si $d$ divise $\text{PGCD}(a;b)$, comme $\text{PGCD}(a;b)$ divise $a$ et $b$, alors $d$ divise aussi $a$ et $b$ par transitivité.
En conclusion, les diviseurs de $\text{PGCD}(a;b)$ sont bien les diviseurs communs à $a$ et $b$.

On a $45|n$ donc il existe $m\in \mathbb{N}$ tel que $n=45m$.
Or $n⩽450$ donc $m⩽10$.
De plus, $45=\text{PGCD}(n;270)=\text{PGCD}(45m;45\times 6)=45\times \text{PGCD}(m;6)$, donc $\text{PGCD}(m;6)=1$. On en déduit qui $m\in \{1;5;7\}$ donc $n\in \left\{45;225;315\right\}$.

Exercices

41

et

42

p. 133.