ExerciceMaths expertes, chapitre 7 — PGCD · PGCD et algorithme d'Euclide

Exercice 6

DémonstrationCalcul

Soit $n\in\mathbb{N}^{*}$ . On note $d=\mathrm{PGCD}(n,n+6)$ .

1. Montrer que $d$ divise $6$ . Quelles sont les valeurs possibles de $d$  ?

2. Déterminer $d$ selon le reste de la division euclidienne de $n$ par $6$ .

3. Vérifier le résultat avec $n=9$ , $n=10$ , $n=11$ et $n=12$ .

Corrigé

1. $d$ divise $n$ et $n+6$ , donc leur différence $(n+6)-n=6$ . Les valeurs possibles sont les diviseurs positifs de $6$ : $\boxed{d\in\{1\,;2\,;3\,;6\}}$

2. Réciproquement, un diviseur commun à $n$ et $6$ divise $n+6$ . Les diviseurs communs de $n$ et $n+6$ sont donc exactement ceux de $n$ et $6$ , d'où $d=\mathrm{PGCD}(n,6)$ . Si $n=6q+r$ avec $0\leqslant r\leqslant 5$ , la Proposition 2 donne $d=\mathrm{PGCD}(6,r)$ lorsque $r\neq 0$ , et $d=6$ lorsque $r=0$ :

Reste de $n$ modulo $6$	$0$	$1$	$2$	$3$	$4$	$5$
$d=\mathrm{PGCD}(n,n+6)$	$6$	$1$	$2$	$3$	$2$	$1$

3. $n=9$ a pour reste $3$ : $\mathrm{PGCD}(9,15)=3$ . $n=10$ a pour reste $4$ : $\mathrm{PGCD}(10,16)=2$ . $n=11$ a pour reste $5$ : $\mathrm{PGCD}(11,17)=1$ . $n=12$ a pour reste $0$ : $\mathrm{PGCD}(12,18)=6$ . Les quatre valeurs sont conformes au tableau.

Énoncé PDF, p. 1 Corrigé PDF, p. 5 Toute la feuille Le cours

Dans l'édifice

PGCD, théorème de Bézout, lemme de Gauss

Thèmes

pgcd

Notions

PGCD