Démonstration de l’algorithme d’Euclide (réf 1555) chapitre 3 PGCD, théorèmes de Bezout et de Gauss, nombres premiers, Option maths expertes, séquence 1 PGCD

De "proche en proche" on a donc PGCD$(a,b)=$PGCD$(b,r_0)=$PGCD$(r_0,r_1)$ où $r_1$ est le reste de la division euclidienne de $b$ par $r_0$.
PGCD$(r_0,r_1)=$PGCD$(r_1,r_2)$ où $r_2$ est le reste de la division euclidienne de $r_0$ par $r_1$.
PGCD$(r_1,r_2)=$PGCD$(r_2,r_3)$ où $r_3$ est le reste de la division euclidienne de $r_1$ par $r_2$.
On note $r_n$ est le reste de la divsion euclidienne de $r_{n-2}$ par $r_{n-1}$.
Montrer que la suite des restes est strictement décroissante.

Rappel cours

Division euclidienne dans $\mathbb{Z}$
Soient $a$ et $b$ deux entiers relatifs avec $b\neq 0$.
La division euclidienne de $a$ par $b$ c'est associer un unique couple $(q;r)$ avec $q$ entier relatif et $r$ entier naturel tel que $a=bq+r$ avec $0\leq r< |b|$.
$a$ est le dividende, $b$ le diviseur, $q$ est le quotient et $r$ le reste.

Solution

Vous devez être inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION

En déduire qu'il existe $n\in \mathbb{N}$ tel que $r_{n+1}=0$ et que PGCD$(a,b)=r_n$ avec $r_n\neq 0$

Solution

Vous devez être inscrit pour accéder à ce contenu gratuitement!
INSCRIPTION

Inscrivez-vous pour accéder à ce contenu gratuitement!

INSCRIPTION

Ressource précédente: QCM séquence 1 PGCD et algorithme d’Euclide (réf 1554) Ressource suivante: Utiliser les propriétés du PGCD (réf 1556)