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

Voir exercice

67

p. 134.

Les diviseurs positifs de 700 sont les suivants.


Si \text{PGCD} \lparen n \, ; 700\rparen=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} \lparen n \, ; 700\rparen \geqslant 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} \lparen a \, ; b\rparen = b.
Sinon, on effectue la division euclidienne de a par b.
Tant que le reste r est non nul, on remplace \lparen a \, ; b\rparen par \lparen b \, ; r\rparen et on recommence. \text{PGCD} \lparen a \, ; b\rparen est le dernier reste non nul.

450 = \textcolor{#b1354f}{198} \times 2 + \textcolor{#5eb45e}{54}
\textcolor{#b1354f}{198} = \textcolor{#5eb45e}{54} \times 3 + \textcolor{#2c85bb}{36}
\textcolor{#5eb45e}{54} = \textcolor{#2c85bb}{36} \times 1 + \textcolor{#7d3581}{18}
\textcolor{#2c85bb}{36} = \textcolor{#7d3581}{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 \lparen a \, ; b\rparen \in \Z^2. On suppose que a et b ne sont pas simultanément nuls et on note d \in \Z un diviseur commun à a et b.
Montrons que d divise \text{PGCD} \lparen a \, ; b\rparen. 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_mr_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} \lparen a \, ; b\rparen est le dernier terme non nul de cette suite, \text{PGCD} \lparen a \, ; b\rparen est divisible par d.
Réciproquement, si d divise \text{PGCD} \lparen a \, ; b\rparen, comme \text{PGCD} \lparen a \, ; b\rparen divise a et b, alors d divise aussi a et b par transitivité.
En conclusion, les diviseurs de \text{PGCD} \lparen a \, ; b\rparen sont bien les diviseurs communs à a et b.

On a 45 \vert n donc il existe m \in \N tel que n = 45m.
Or n \leqslant 450 donc m \leqslant 10.
De plus, 45= \text{PGCD} \lparen n \, ; 270\rparen = \text{PGCD} \lparen 45m \, ; 45 \times 6\rparen = 45 \times \text{PGCD} \lparen m \, ; 6\rparen, donc \text{PGCD} \lparen m \, ; 6\rparen = 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.