PGCD et PPCM de deux entiers :
Soient a et b deux entiers naturels au moins égaux à 2. Le PGCD de a et b est égal au produit des facteurs premiers communs de a et de b avec pour chacun
I PGCD et PPCM de deux nombres entiers
L'ensemble des diviseurs communs à deux entiers non nuls est non vide et majoré. • Soit n un entier naturel non nul. Un diviseur commun à 2n ? 1 et n + 3
Nombres premiers. pgcd et ppcm - Lycée dAdultes
27 juin 2016 Définition 2 : On dit d'un entier a est un nombre premier si et seulement si il admet exactement deux diviseurs 1 et lui-même.
PGCD - PPCM Théorèmes de Bézout et de Gauss
15 juil. 2016 Définition 1 : Soit a et b deux entiers relatifs non nuls. L'ensemble des diviseurs communs à a et b admet un plus grand élément D appelé plus ...
PGCD et PPCM
Le PGCD de deux entiers relatifs est le plus grand entier qui les divise simultanément. (si les deux nombres sont zéro on définit le PGCD comme zéro).
Séance de travaux pratiques n° 2
cet algorithme permet de calculer le PGCD et le PPCM de deux entiers variables a b
Arithmétique dans Z
2 pgcd ppcm
PPCM et PGCD
La première méthode peut être généralisée et utilisée quand on cherche le PPCM de plus de deux nombres. Remarque :les multiples communs à deux nombres sont les
PGCD ET NOMBRES PREMIERS
Yvan Monka – Académie de Strasbourg – www.maths-et-tiques.fr. 1. PGCD ET NOMBRES PREMIERS. I. PGCD de deux entiers. 1) Définition et propriétés. Exemple :.
Cours Terminale S PGCD et PPCM 1. Plus grand commun diviseur
Plus grand commun diviseur. 1.1 Diviseurs communs à deux entiers positifs. Pour tout entier naturel n on note D(n) l'ensemble des diviseurs de n.
Cours Terminale S PGCD et PPCM
1. Plus grand commun diviseur
1.1 Diviseurs communs à deux entiers positifs
Pour tout entier naturel n, on note D(n) l'ensemble des diviseurs de n. On note D(a; b) l'ensemble des diviseurs communs à a et b, c'est-à-dire D(a; b) = D(a) ? D(b). Le plus grand élément de D(a; b) est appelé PGCD de a et b , noté PGCD(a; b). Exemple: Le PGCD de 24 et 36 est 12; celui de 25 et 12 est 1.Propriétés:
Pour tout entier naturel n, D(n; 0) = D(n). En effet, D(n; 0) = D(n) ? ? = D(n).PGCD(a; b) ? a et PGCD(a; b) ? b. En effet, les diviseurs de a sont inférieurs à a , de même pour b.
Si b divise a, alors PGCD(a; b) = b. En effet, Si b divise a, b ? D(a; b).PGCD(a; b) = PGCD(b; a).
PGCD(a; 1) = 1.
PGCD(a; a) = a.
Pour tout k entier naturel non nul, PGCD(ka; kb) = k ?PGCD(a; b). Démonstration à l'aide de l'algorithme
d'Euclide, vu juste après.1.2 Recherche du PGCD : Algorithme d'Euclide:
a) Propriété : Soit a = bq + r la division euclidienne de a par b . Alors D(a; b) = D(b; r) .Si r = 0, alors PGCD(a; b) = b.
Si r ? 0, alors PGCD(a; b) = PGCD(b; r).
Démonstration : Soit c un diviseur commun de a et de b. Il existe deux entiers a' et b' tels que a = ca' et b = cb'.
Si a = bq + r est la division euclidienne de a par b , alors r = a - bq = ca' - cb'q = c(a' - b'q), et c divise r, donc
est un diviseur commun de b et de r. Ainsi D(a; b) ? D(b; r).Réciproquement, soit d un diviseur commun de b et de r. Il existe deux entiers b' et r' tels que b = db' et r = dr'.
Si a = bq + r est la division euclidienne de a par b , alors a = db'q + dr' = d(b'q + r'), et d divise a, donc est un
diviseur commun de a et de b. Ainsi D(b; r) ? D(a; b). Finalement, D(a; b) = D(b; r), et PGCD(a; b) = PGCD(b; r). b) Algorithme d'Euclide: Pour rechercher le PGCD de a et de b, on effectue les divisions euclidiennes successives :a = bq + r avec 0 ? r < b ; puis b = rq1 + r1 avec 0 ? r1 < r ; puis r = r1 q2 + r2 avec 0 ? r2 < r1 ; etc... jusqu'à ce
que le reste soit nul. Alors le PGCD de a et de b est le dernier reste non nul. Exemple : On cherche PGCD(48; 63) : On a successivement :63 = 1 ? 48 + 15, puis 48 = 3 ? 15 + 3, puis 15 = 5 ? 3 + 0. Donc PGCD(48; 63) = 3.
c) Propriété : D(a; b) = D(g) où g est le PGCD de a et de b.2. Nombres premiers entre eux
Définition: Soient a et b deux entiers naturels non nuls. On dit que a et b sont premiers entre eux si PGCD(a; b) = 1.Propriété: Soit a un entier naturel non nul. Si p est un nombre premier qui ne divise pas a, alors a et p sont
premiers entre eux. Soient a et b deux entiers naturels non nuls et d leur PGCD. Alors a d et b d sont premiers entre eux.3. Théorème de Bezout :
Théorème : Soient a et b deux entiers relatifs non nuls.a et b sont premiers entre eux si et seulement si il existe des entiers relatifs u et v tels que au + bv = 1.
Démonstration : Supposons a et b sont premiers entre eux; considérons l'ensemble E des nombres au + bv avec u
et v entiers relatifs. E contient des entiers naturels non nuls : si a l'est, E contient a = a?1 + b?0. si a est négatif,
E contient - a = a?(-1) + b?0. Donc E contient un plus petit entier naturel m = au1 + bv1 . Montrons que m
divise a et b: La division de a par m donne a = mq + r = (au1 + bv1)q + r , avec 0 ? r < m.Or r = (au1 + bv1)q - a = a(u1q - 1) + b(v1q) de la forme au + bv. Comme m est le plus petit entier naturel de la
forme au + bv, alors r = 0. Donc m divise a. De la même manière, m divise b. Or a et b sont premiers entre eux,
donc m = 1.Supposons qu'il existe des entiers relatifs u et v tels que au + bv = 1. Le pgcd(a; b) = g divise a et b et tout nombre
de la forme au + bv. Donc g = 1, et a et b sont premiers entre eux.Corollaire: Soient a et b deux entiers relatifs et d leur PGCD. Alors il existe des entiers relatifs u et v tels que
au + bv = d.4. Théorème de Gauss :
Théorème : Soient a et b deux entiers relatifs non nuls et c un entier relatif. Si a divise bc et si a est premier avec
b alors a divise c.Démonstration : Comme a et b sont premiers entre eux, il existe des entiers relatifs u et v tels que au + bv = 1.
Donc auc + bvc = c. Or a divise auc et divise bc, donc a divise auc + bvc = c.Corollaires:
?Si un entier relatif c est divisible par deux entiers a et b premiers entre eux, alors c est divisible par le produit
ab. ?Si un nombre premier p divise le produit ab, alors il divise au moins l'un des facteurs a et b.5. Plus petit commun multiple
2.1 Multiples communs à deux entiers positifs
Pour tout entier naturel n, on note M(n) l'ensemble des multiples de n. M(n) = {k , k = nq avec q ?? }.
On note M(a; b) l'ensemble des multiples communs à a et b, c'est-à-dire M(a; b) = M(a) ? M(b). Le plus petit élément de M(a; b) est appelé PPCM de a et b , noté PPCM(a; b). Exemple: Le PPCM de 24 et 36 est 72; celui de 25 et 12 est 300.2.2 Propriétés :
Le PGCD(a; b) divise le PPCM(a; b).
PGCD(a; b) ? PPCM(a; b) = ab.
Pour tout k entier naturel non nul, PPCM(ka; kb) = k ?PPCM(a; b).M(a; b) = M( PPCM(a ; b)).
quotesdbs_dbs29.pdfusesText_35[PDF] E = m c2 l équation de Poincaré, Einstein et Planck
[PDF] SECOND DEGRÉ - Maths-et-tiques
[PDF] Démonstrations combinatoires
[PDF] 1 Démonstrations du formulaire de trigonométrie - Free
[PDF] Primitives et intégrales
[PDF] Charlemagne sur Internet - Statim
[PDF] III- Raisonnement par récurrence
[PDF] Raisonnement par récurrence - Math France
[PDF] Planche no 2 Raisonnement par récurrence : corrigé - Math France
[PDF] Planche no 2 Raisonnement par récurrence : corrigé - Math France
[PDF] RÉUSSIR L 'ÉPREUVE DE PHYSIQUE Baccalauréat 2015 - MENFP
[PDF] Intégration et primitives - Lycée d 'Adultes
[PDF] Démonstration de la formule de conjugaison pour les dioptres
[PDF] La théorie de la relativité générale - UdPPC
