Propriété - Définition (voir démonstration 01)
Si r = 0 alors a = b x q avec q ? IN
PGCD Théorème de Bézout Théorème de Gauss
Exemple : On a donc PGCD (12 ; 63) = 3. Propriété 1 : Soient a et b deux entiers naturels non nuls. Si b divise a alors D (a ; b) = D
PGCD ET NOMBRES PREMIERS
Réciproquement si D un diviseur de a et b alors D divise r = a – bq et donc D est un diviseur de b et r. On en déduit que l'ensemble des diviseurs communs de a
Théorème de Gauss Terminale S Spécialité - PGCD - THEOREME
Réciproquement si d divise b alors
PGCD et PPCM de deux entiers :
(division euclidienne de a par b). Alors : D(a)?D(b) = D(b)?D(r) et pgcd(a ; b)=pgcd(b ; r). Démonstration : : 1. Si a divise b tout diviseur de a est un
1 PGCD
Montrons que D ? D/. – Soit d ? D alors d est un diviseur commun de a et b . – Par définition si d divise a et b alors d divise .
Sur le pgcd
Si d est le pgcd de a et b et si e est un diviseur de a et b alors e divise d. Démonstration. On note d'abord que le cas o`u a ou b est nul est trivial.
PGCD - PPCM Théorèmes de Bézout et de Gauss
15-Jul-2016 Dans le sens ? : (réciproquement). On suppose qu'il existe deux entiers u et v tels que : au + bv = 1. Si D = pgcd(a b) alors D divise a et b ...
Chapitre 2 Larithmétique des entiers
Si d est un diviseur commun `a a et b alors on sait que d
CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE
Il existe une solution x de ax ? b (mod n) si et seulement si d = pgcd(a n) En effet
[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques
Démonstration de c : Si b divise a alors tout diviseur de b est un diviseur de a Donc le plus grand diviseur de b est un diviseur de a 2) Algorithme d'Euclide
[PDF] Propriété - Définition (voir démonstration 01)
Soit d un diviseur commun à a et b (on peut supposer que b ? a) • Si b divise a alors PGCD(a ; b) = b donc D =
[PDF] PGCD - PPCM Théorèmes de Bézout et de Gauss - Lycée dAdultes
15 juil 2016 · Si b divise a alors pgcd(a b) = b • Pour tout entier naturel k non nul on a : pgcd(ka kb) = k pgcd(a b)
[PDF] Sur le pgcd
Si d est le pgcd de a et b et si e est un diviseur de a et b alors e divise d Démonstration On note d'abord que le cas o`u a ou b est nul est trivial
[PDF] PGCD - THEOREME DE GAUSS
Si b divise a alors PGCD(a; b) = b Démonstration Les diviseurs communs à a et à b sont les diviseurs de b En effet si d divise a et b
[PDF] PGCD – NOMBRES PREMIERS ENTRE EUX - Pierre Lux
Un entier naturel qui divise a et qui divise b est appelé diviseur commun à a et b Si b divise a alors PGCD(a ; b) = b donc D = b donc d divise D
[PDF] chapitre 3 : congruences et arithmétique modulaire
La condition que d divise b est nécessaire c'est à dire si la congruence a une solution alors d divise b En effet si on a ax ? b (mod n) alors il existe
[PDF] Chapitre 2 Larithmétique des entiers
Preuve — Il suffit de vérifier que pgcd(a b) est bien le plus grand des diviseurs communs `a a et b Si d est un diviseur commun `a a et b alors on sait
[PDF] Terminale S Spécialité Cours : PGCD - Théorème de Bézout
Si d est un diviseur commun à a et b alors il divise aussi a et bq Il divise donc aussi r = a – bq Donc d est un diviseur commun à b et r
[PDF] 1 PGCD
Par définition si d divise a et b alors d divise Soit PGCD(a; b) = d alors il existe a' et b' deux entiers premiers entre eux tels que : a = da/ et b
Soient a et b deux entiers naturels non nuls.
Un entier naturel qui divise a et qui divise b est appelé diviseur commun à a et b. L'ensemble des diviseurs communs à a et à b possède un plus grand élément que l'on appelle le
plus grand commun diviseur de a et b, on le note PGCD(a ; b).Démonstration 01 (retour au cours)
a et b sont deux entiers naturels non nuls.Considérons l'ensemble
D(a ; b), ensemble des diviseurs communs à a et b. Le nombre 1 est un diviseur commun à a et b.D(a ; b) est donc une partie non vide de IN.
De plus on sait que tout diviseur commun à a et b sera inférieur ou égal à a et à b.
Donc D(a ; b) est une partie finie de IN.
D(a ; b) a donc un plus grand élément que l'on peut obtenir en rangeant dans l'ordre croissant (ou
décroissant) les éléments de D(a ; b). C'est ce plus grand élément de D(a ; b) qui est noté PGCD(a ; b)Propriétés
(voir démonstration 02)Soient a et b deux entiers naturels non nuls.
On a PGCD(a ; b) a ; PGCD(a ; b) b ; PGCD(a ; b) = PGCD(b ; a)Si b divise a, on a PGCD(a ; b) = b , en particulier PGCD(a ; 1) = 1 et PGCD(a ; a) = a Démonstration 02 (retour au cours)
a étant un entier naturel, on sait que tous les diviseurs de a sont inférieurs ou égaux à a.
PGCD(a ; b) est un diviseur de a, donc PGCD(a ; b) ab étant un entier naturel, on sait que tous les diviseurs de b sont inférieurs ou égaux à b.
PGCD(a ; b) est un diviseur de b, donc PGCD(a ; b) bIl est immédiat que les diviseurs communs à a et b, sont aussi les diviseurs communs à b et a.
Donc PGCD(a ; b) = PGCD(b ; a)
Si b divise a, alors b est un diviseur de a
Mais b est aussi un diviseur de b
Donc b est un diviseur commun à a et b ,
PGCD(a ; b) étant le plus grand des diviseurs communs à a et b, on a donc PGCD(a ; b) b Or on a vu précédemment que PGCD(a ; b) bOn en déduit :
PGCD(a ; b) = b
En prenant b = 1, et comme 1 divise a, on a PGCD(a ; 1) = 1 (résultat qui est par ailleurs évident)
En prenant b = a, et comme a divise a, on a PGCD(a ; a) = a (résultat qui est par ailleurs évident)
Propriété
(voir démonstration 03)Soient a et b deux entiers naturels non nuls. Soient q et r le quotient et le reste de la division euclidienne de a par b. (On a a = b x q + r )
Alors Si r = 0, PGCD(a ; b) = b
Si r 0, PGCD(a ; b) = PGCD(b ; r)
Démonstrations des propriétés d'arithmétique 2Démonstration 03 (retour au cours)
a et b sont deux entiers naturels non nuls. q et r sont le quotient et le reste de la division euclidienne de a par b.On a a = b
x q + r avec q IN , r IN et 0 r < bSi r = 0, alors a = b
x q avec q IN , donc b divise a et par conséquent PGCD(a ; b) = bSi r 0,
Considérons d un diviseur commun à a et b.On peut écrire r = a - b
x q Comme d divise a et b, on en déduit que d divise r Donc d est un diviseur commun à b et r. On a donc D(a ; b) D(b ; r) Considérons d un diviseur commun à b et r.On sait que a = b
x q + r Comme d divise b et r, on en déduit que d divise a Donc d est un diviseur commun à a et b. On a donc D(b ; r) D(a ; b) On a donc démontré que D(a ; b) = D(b ; r) Le plus grand élément de D(a ; b) est donc aussi le plus grand élément de D(b ; r) c'est-à-dire PGCD(a ; b) = PGCD(b ; r) Propriété - Algorithme d'Euclide (voir démonstration 04)Soient a et b deux entiers naturels non nuls.
On définit la suite r
n d'entiers naturels de la façon suivante : r 0 = b ; r 1 est le reste de la division euclidienne de a par bPour n 1 : si r
n = 0 alors r n+1 = 0 si r n0 alors r
n+1 est le reste de la division euclidienne de r n-1 par r nAlors il existe un entier n
0 tel que r n 00 et pour tout n > n
0 , r n = 0On a PGCD(a ; b) = r
n 0Remarque
En effectuant ainsi des divisions euclidiennes successives: de a par b, puis du diviseur par le reste, ...
le premier reste non nul est le PGCD de a et de b. C'est l'algorithme d'EuclideSuivant les nombres a et b, le nombre d'itérations à effectuer peut être plus ou moins grand.
Sachant que PGCD(a ; b) = PGCD(b ; a) on aura toujours intérêt à prendre b aDémonstration 04 (retour au cours)
a et b sont deux entiers naturels non nuls.La suite r
n d'entiers naturels est définie par : r 0 = b ; r 1 est le reste de la division euclidienne de a par bPour n 1 : si r
n = 0 alors r n+1 = 0 si r n0 alors r
n+1 est le reste de la division euclidienne de r n-1 par r nSupposons que pour tout entier n, on a r
n 0Alors pour tout entier n, r
n+1 est le reste de la division euclidienne de r n-1 par r n D'après l'encadrement du reste dans une division euclidienne on a r n+1 < r nOn a alors r
1 < r 0 donc r 1 < b donc r 1 b - 1 r 2 < r 1 donc r 2 r 1 - 1 donc r 2 b - 2 On pourrait alors démontrer par récurrence que pour tout n r n b - nOn aurait alors r
b+1 b - (b + 1) c'est-à-dire r b+1 -1 ce qui est absurde puisque r b+1 INEn supposant que r
n0 pour tout entier n, on aboutit à une contradiction.
Démonstrations des propriétés d'arithmétique 3Il existe donc un entier n tel que r
n = 0 Considérons l'ensemble E des entiers n tels que r n = 0 Cet ensemble est une partie non vide de IN. Elle a donc un plus petit élément n 1On a donc r
n 1 = 0 et d'après la définition de la suite (r n ) il est immédiat que r n = 0 pour tout n n 1Posons n
0 = n 1 - 1Puisque n
1 est le plus petit élément de E, n 0E donc r
n 0 0De plus si n > n
0 on a n n 1 et par conséquent r n = 0 donc r n = 0 pour tout n tel que n > n 0 On a vu que lorsque r est le reste non nul de la division euclidienne de a par b, on aPGCD(a ; b) = PGCD(b ; r)
En utilisant cette propriété avec les éléments de la suite (r n ) pour n n 0 on peut écrire :PGCD(a ; b) = PGCD(a ; r
0 ) = PGCD(r 0 ; r 1 ) = PGCD(r 1 ; r 2 ) = ... = PGCD(r n 0-1 ; r n 0Comme de plus r
n 0+1 = r n 1 = 0 , cela signifie que r n 0-1 est divisible par r n 0 et donc PGCD(r n 0-1 ; r n 0 = r n 0On a alors obtenu PGCD(a ; b) = r
n 0Propriété (voir démonstration 05)
Soient a et b deux entiers naturels non nuls.
L'ensemble des diviseurs communs à a et à b est l'ensemble des diviseurs de leur PGCD.Démonstration 05 (retour au cours)
a et b sont deux entiers naturels non nuls.Notons D = PGCD(a ; b)
Soit d un diviseur de D. d divise D et D divise a, donc d divise a d divise D et D divise b, donc d divise b.Donc d est un diviseur commun à a et b.
Tout diviseur du PGCD est un diviseur commun à a et b. Soit d un diviseur commun à a et b. (on peut supposer que b a) Si b divise a, alors PGCD(a ; b) = b, donc D = b, donc d divise DSi b ne divise pas a.
Écrivons la division euclidienne de a par b, a = b x q + r avec 0 < r < bOn a D = PGCD(a ; b) = PGCD(b ; r)
Si r divise b, alors D = PGCD(b ; r) = r,
D'autre part puisque d divise a et b, alors d divise r = a - b x q, donc d divise D Si r ne divise pas b, on peut alors recommencer l'opération. Or, d'après l'algorithme d'Euclide, on obtiendra D = PGCD(r n-1 ; r n avec r n le dernier reste non nul, c'est-à-dire avec r n diviseur de r n-1 . Donc D = r n A chaque étape on pourra écrire que d divise r i et par conséquent d divise r nOn aura donc démontré que d divise D.
Tout diviseur commun à a et b est donc un diviseur de leur PGCD. L'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de leur PGCD.quotesdbs_dbs22.pdfusesText_28[PDF] pgcd(ka kb)=k pgcd(a b)
[PDF] conversion notes erasmus
[PDF] correspondance notes lettres
[PDF] conversion notes québec france
[PDF] note sur 20 en gpa
[PDF] tableau de conversion de notes european credit transfer system
[PDF] tableau de conversion des notes
[PDF] b2i adultes ressources
[PDF] b2i adultes greta
[PDF] b2i adultes exercices
[PDF] compétences b2i cm2
[PDF] compétences tice cycle 3 2016
[PDF] compétences tice cycle 2
[PDF] tice programmes 2016