MATHS-LYCEE$a$ et $b$ sont deux entiers naturels non nuls avec $b
Montrer que PGCD$(a,b)=$PGCD$(b,r_0)$.
On peut écrire $a=bq_0+r_0$ soit $a-bq=r_0$
On pose $D=$PGCD$(a,b)$ et $d_0=$PGCD$(b,r_0)$
On a $a=bq_0+r_0$ donc $r_0=a-bq_0$
$D$ divise $a$ et $b$ donc $D$ divise toute combinaison linéaire de $a$ et $b$ soit $D$ divise $a-bq_0=r_0$
$D=$PGCD$(a,b)$ donc $D$ divise $b$ et on a $D$ divise $r_0$
donc $D$ est un diviseur commun à $b$ et $r_0$
donc $D\leq d$ puisque $d$ est le plus grand diviseur commum à $b$ et $r_0$
De même on a $a=bq_0+r_0$ et $d=$PGCD$(b,r_0)$ donc $d$ divise $b$ et divise $r_0$
donc divise toute combinaison linéaire de $b$ et $r_0$
donc $d$ divise $bq_0+r_0=a$
donc $d$ divise $a$ et $b$
donc $d\leq D$ puisque $D$ est le plus grand diviseur commun à $a$ et $b$
On a donc $D\leq d$ et $d\leq D$ donc $D=d$
On a $a=bq_0+r_0$ donc $r_0=a-bq_0$
$D$ divise $a$ et $b$ donc $D$ divise toute combinaison linéaire de $a$ et $b$ soit $D$ divise $a-bq_0=r_0$
$D=$PGCD$(a,b)$ donc $D$ divise $b$ et on a $D$ divise $r_0$
donc $D$ est un diviseur commun à $b$ et $r_0$
donc $D\leq d$ puisque $d$ est le plus grand diviseur commum à $b$ et $r_0$
De même on a $a=bq_0+r_0$ et $d=$PGCD$(b,r_0)$ donc $d$ divise $b$ et divise $r_0$
donc divise toute combinaison linéaire de $b$ et $r_0$
donc $d$ divise $bq_0+r_0=a$
donc $d$ divise $a$ et $b$
donc $d\leq D$ puisque $D$ est le plus grand diviseur commun à $a$ et $b$
On a donc $D\leq d$ et $d\leq D$ donc $D=d$
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.
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.
$r_n$ est le reste de la divsion euclidienne de $r_{n-2}$ par $r_{n-1}$ donc il existe un entier naturel $q_n$ tel que $r_{n-2}=q_n\times r_{n-1}+r_{n-2}$ avec $r_{n-2}< r_{n-1}$ (définition de la division euclidienne)
La suite des restes est strictement décroissante et $r_n\in \mathbb{N}$
donc il xiste un reste nul et donc $n$ entier naturel tel que $r_{n+1}=0$
$r_{n+1}=0$ et $r_{n+1}$ reste de la division euclidienne de $r_{n-1}$ par $r_n$ donc $r_{n}$ divise $r_{n-1}$
$r_{n}$ divise $r_{n-1}$ donc PGCD$(r_{n-1},r_n)=r_n$
or PGCD$(a,b)\neq 0$
donc il xiste un reste nul et donc $n$ entier naturel tel que $r_{n+1}=0$
$r_{n+1}=0$ et $r_{n+1}$ reste de la division euclidienne de $r_{n-1}$ par $r_n$ donc $r_{n}$ divise $r_{n-1}$
$r_{n}$ divise $r_{n-1}$ donc PGCD$(r_{n-1},r_n)=r_n$
or PGCD$(a,b)\neq 0$
Attention les fonctions ci-dessous sont désactivées en mode "visiteur", créez un compte MATHS-LYCEE.FR (gratuit)
Cours nº 1579
Vous pouvez retourner sur le cours après avoir vu cette vidéo.
PGCD et algorithme d'Euclide
- PGCD
- nombres premiers entre eux
- algorithme d'Euclide
infos cours
| 30mn
série 2 : Démonstrations de cours