Publications MATHS-LYCEE.FR
Aide en ligne avec WhatsApp*, un professeur est à vos côtés à tout moment! Essayez!
Un cours particulier à la demande!
Envoyez un message WhatsApp au 07 67 45 85 81 en précisant votre nom d'utilisateur.*période d'essai ou abonnés premium(aide illimitée, accès aux PDF et suppression de la pub)
$a$ et $b$ sont deux entiers naturels non nuls avec $b
On note $q_0$ et $r_0$ le quotient et le reste de la division euclidienne de $a$ par $b$.
Montrer que PGCD$(a,b)=$PGCD$(b,r_0)$.
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.
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.
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$
Attention les fonctions ci-dessus sont désactivées en mode "visiteur", créez un compte MATHS-LYCEE.FR (gratuit)
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-dessus sont désactivées en mode "visiteur", créez un compte MATHS-LYCEE.FR (gratuit)