PGCD et PPCM de deux entiers : PDF

Calcul-du-PPCM.pdf

Calcul du PPCM. Le Plus Petit Commun Multiple. Définition : Le multiple commun qui est le plus petit possible et qui sera capable de s'appliquer à plusieurs

Leçon 7 : Le plus petit commun multiple (ppcm) et le plus grand

comment s'obtiennent les nombres de ra deuxième ligne ? 3. Ecrire les entiers b) Calculer ppcm (3756375) et pgcd (375

fx-92 Collège

– [Calcul numérique] > [PPCM]. 9 15. Valeur absolue. Lorsque vous effectuez un calcul Comment calculer sin2 x ? → Par exemple pour calculer sin2 30 = 1. 4.

Tableau-comparatif-du-PGCD-et-PPCM.pdf

Trouver le premier multiple commun à 2 nombres. • Opérations avec les fractions. ( addition – soustraction). Travail sur une seule fraction.

MATHÉMATIQUES 8E

Comment peut-on placer des signes "+" entre les chiffres 123456789 pour que ... Calculer le rayon d'un cylindre sachant que son volume est de 1846

Nombres premiers. pgcd et ppcm - Lycée dAdultes

27 Jun 2016 Remarque : Si l'on ne peut pas trouver un tel nombre p alors le nombre est premier. Exemple : • Montrons que 109 est premier. On effectue ...

Synthèse Kit de survie Terminale S CASIO GRAPH35+

Calculs sur les nombres complexes. Pour obtenir le nombre i. Touche OPTN sélectionner CPLX. (touche F3 ) et i (touche F1 ). Dans le

Les plans dexpériences par la méthode TAGUCHI

• COMMENT ? Quels sont les matériels les moyens nécessaires ? • POURQUOI ⇒ Calcul du PPCM - règle de l'orthogonalité. ⇒ Calcul du nombre de degré de ...

Mathématique

Comment reconnaître l'utilisation du PGCD ou PPCM dans un contexte? • Si nous devons trouver quelque chose qui arrivera de façon répétitive ou cyclique ou qu'il

Arithmétique des polynômes

RkPk = D. On peut généraliser aussi le PPCM `a une famille de polynômes de la même mani`ere. Test 395. Calculer le PPCM de la famille (X − 1 X − 2

Avec la calculatrice speciale collège

Avec cette calculatrice Spéciale Collège le calcul du PPCM de deux nombres est enfin possible car une touche a été ajoutée. ? Pour déterminer le PPCM

ppcm.pdf

b) Deuxième méthode (utilisable si on a déjà calculé le PGCD). On utilise le fait que le produit du PPCM par le PGCD est égal au produit des deux nombres de

Calcul du PGCD

Calcul du PPCM. Le Plus Petit Commun Multiple. Définition : Le multiple commun qui est le plus petit possible et qui sera capable de s'appliquer à.

Leçon 7 : Le plus petit commun multiple (ppcm) et le plus grand

2. comment s'obtiennent les nombres de ra deuxième ligne ? Exemple I : Calculer ppcm (3 15108) et pgcd (3 l5

Nombres premiers. pgcd et ppcm - Lycée dAdultes

27 juin 2016 Remarque : Si l'on ne peut pas trouver un tel nombre p alors le nombre est premier. Exemple : • Montrons que 109 est premier.

Tableau-comparatif-du-PGCD-et-PPCM.pdf

PPCM. Définition. Plus grand diviseur commun. Plus petit multiple commun. Application Calcul du PGCD et du PPCM de : 98 et 48.

Synthèse Kit de survie Terminale S TI 83 Premium CE

Touche math et choix 1:>Frac après le calcul approché ou bien Pour calculer P(X> 4) on peut saisir comme borne ... Instructions 8: ppcm et 9: pgcd.

Synthèse Kit de survie Terminale S CASIO GRAPH35+

calcul. 3 calculs saisies instruction REPLAY. Le calcul modifié. Dérivation - Intégration Sélectionner LCM(touches F6 puis F3 ) pour le PPCM.

PGCD et PPCM de deux entiers :

Pour éliminer n on calcule A?2B. A?2B = 2n+1?2(n?5)= 11 donc A = 2B+11. PGCD(A ; B)=PGCD(B ; 11). Comme 11 est un nombre premier

PGCD et PPCM de deux entiers :

Table des matières

IPlus grand commun diviseur de deux entiers :. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

IIDéterminationdu PGCD par l"algorithmed"Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

IIIEntierspremiers entre eux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

IVThéorème de Gauss et applications:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

VPetit théorème de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

VIPlus petit commun multiplede deux entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

I Plus grand commun diviseur de deux entiers :

Définition :

Soientaetbdeux entiers naturels non nuls. On noteD(a) l"ensemble des diviseurs dea.

Le plusgrandélémentdeD(a)D(b), ensembledesdiviseurspositifscommunsàaet àb,est leplusgrand

commun diviseurdeaetb, ou encore PGCD deaetb. On le note pgcd(a;b) ou PGCD(a;b)

Casparticuliers :

pgcd(a;a)a;pgcd(1; a)=1 ; pgcd(a; 0)apouranon nul. Remarque :le PGCD de deux entiers naturels est un entier au moins égal à 1.

Propriété :

Soientaetbdeux entiers naturels au moins égaux à 2. Le PGCD deaetbest égal au produitdesfacteurspremierscommunsdeaet deb,avec pourchacund"eux, l"exposant le plus petit de ceux qu"il a dansaet dansb.

Démonstration ::

Soitdle PGCD deaet deb, naturels supérieurs ou égaux à 2. Commeddivisea, sa décomposition en facteurs

premiers est formée des facteurs premiers deaavec un exposant au plus égal à celui qu"ils sont dans dansa. De

même pourb.

Ainsi, la décomposition dedcomprend les facteurs premiers àaet àb, avec un exposant au plus égal au plus

petit des exposants dans les décompositions deaet deb.

Commedest le plus grand des diviseurs communs, ces exposants sont égaux au plus petit de ceux se trouvant

dans la décompositiondeaet deb.

Exemple :cherchons le PGCD de 700 et de 90.

Remarque :Soienaetbdes entiers relatifs non nuls simultanément. CommeD(a)D(a), le PGCD deaetbest le même que celui deaet deb. 1

TABLE DES MATIÈRES

On peut ainsi se restreindre aux entiers naturels.

Propriété :

1. Siadiviseb, alors pgcd(a;b)a

2. Propriété fondamentale :Soitanon nul tel queabqr. (division euclidienne deaparb).

Alors :D(a)D(b)D(b)D(r) et pgcd(a;b)=pgcd(b;r).

Démonstration ::

1. Siadiviseb, tout diviseur deaest un diviseur deb. Par conséquent :D(a)D(b)D(a) et le plus grand

élément deD(a) esta.

2. Pourdémontrerl"égalitédesdeuxensemblesED(a)D(b) etFD(b)D(r), onmontrequeEestinclus

dansFet queFest inclus dansE. SoitdE. Alorsddiviseb, doncddivisebqet commeddivisea,ddiviseabqr, doncdF. SoitdF.ddivisebdoncbq. Commeddiviser,ddivisebqradoncdE.

Les ensemblesEetFsont égaux, donc ils ont le même plus grand élément. Ainsi : pgcd(a;b)=pgcd(b;r).

Exercice 1 Déterminer le PGCD de 1960 et de 34300.

On a : 1960235172et 34300225273.

On en déduit que PGCD(1960 ; 34300)225172980

Exercice 2 Déterminer le PGCD de deux entiers dépendant den: Déterminer,selon les valeurs den, le PGCD deA2n1 et deBn5. Méthode :on utilisela propriétéfondamentale. Pouréliminern,oncalculeA2B.A2B2n12(n5)11doncA2B11.PGCD(A;B)=PGCD(B; 11). Comme 11 est un nombre premier, le PGCD deBet de 11 ne peut valoir que 1 ou 11.

PGCD(B; 11)11 si et seulement si 11 diviseB.

PGCD(B; 11)11B0(11)n50(11)n5(11).

On en conclut que le PGCD deAetBest 11 lorsquenest congru à 5 modulo 11 et à 1 dans les autres cas.

Exercice 3 Égalité de deux PGCD :

Soientaetbdeux entiers naturels non nuls. Soientx7a5bety4a3b. Montrer que le PGCD dexet deyest égal au PGCD deaet deb. Premièreméthode:7a5b(4a3b)(3a2b)doncpgcd(7a5b; 4a3b)=pgcd(4a3b; 3a2b).

3a2b2(ab)adonc pgcd(4a3b; 3a2b)=pgcd(ab;a)=pgcd(a;b)=pgcd(a;b).

On en déduit que : pgcd(x;y)=pgcd(a;b).

Deuxième méthode :Soitdle PGCD deaetb. Alorsddiviseaetb, donc 7a5bet 4a3bdoncd divise le PGCDddexety. Commeddivise 7a5bet 4a3b,ddivise 7(4a3b)4(7a5b)b. De même,ddivise 3(7a

Page 2/

TABLE DES MATIÈRES

5b)5(4a3b)a. Puisqueddiviseaetb, il divise leur PGCDd.

ddivisedetddivised. Doncdd. II Détermination du PGCD par l"algorithme d"Euclide

(Cet algorithme,c"est-à-dire une suite d"instructions,fut décrit par Euclide au IIIıème siècle avant JC)

Description de l"algorithme d"Euclide

Soientaetbdeux entiers naturels non nuls, avecab.

On diviseaparb.abq1r1, avec 0r1b.

Sir10, alors pgcd(a;b)bpuisquebdivisea.

Sir10, pgcd(a;b)=pgcd(b;r1). On effectue alors la division debparr1.

On a :br1q2r2, avec 0r2r1.

Sir20, alors pgcd(a;b)=pgcd(b;r1)r1.

Sir20, pgcd(b;r1)=pgcd(r1;r2).

Oncontinuela suitede divisionseuclidiennesendivisantunreste par lerestesuivant.Onobtientunesuite de restesr1,r2, ...rn, avecr1r2r3 0. Comme ce sont des entiers, il existe un reste qui est nul. Notonsrnle dernier reste non nul. Alors : pgcd(a;b)=pgcd(b;r1)=pgcd(r1;r2)=...=pgcd(rn1;rn)rn carrndivisern1

Propriété :

Le PGCD de deux entiers non nulsaetbtels quebne divise pasaest le dernier reste non nul de la suite des divisions de l"algorithmed"Euclide.

Corollaires :

1. L"ensemble des diviseurs communs à deux entiersaetbest l"ensemble des diviseurs de leur PGCD.

2. Soitaetbdeux entiers non nuls. Sikest un entier naturel non nul, pgcd (ka;kb)kpgcd (a;b).

Démonstration :

1.D(a)D(b)D(b)D(r1)D(r1)D(r2)D(rn)D(0)D(rn)D(d) puisquedrn.

2. On notedle PGCD deaetbetdcelui dekaetkb.

Commeddiviseaetb,kddivisekaetkb, donckddivise leur PGCDd, donckddivised. d k(kd). (kentier) d divisekaetkb, donckkddivisekaetkb; on en déduit quekddiviseaetb, donc leur PGCDd.kd divised, donck1 etdkd.

Page 3/

TABLE DES MATIÈRES

III Entiers premiers entre eux

Définition :

Deux entiers sont premiers entre eux lorsque leur PGCD est égal à 1.

Remarques:

Cela revient à dire que leurs seuls diviseurs sont -1 et 1.

Il ne faut pas confondre nombre premiers et nombres premiersentre eux. Par exemple, 15 et 22 sont pre-

miers entre eux, mais pas premiers.

Propriété :

Soientaetbdes naturels non nuls etdun diviseur commun deaetb. On poseadaetbdb. Le PGCD deaetbestdsi et seulement siaetbsont premiers entre eux.

Démonstration::

Sidest le PGCD deaetb, soitadaetbdb. On en déduit que : d=pgcd(a;b)=pgcd(da;db)=d pgcd(a;b). Commedest non nul, pgcd(a;b)1 etaetbsont premiers entre eux.

Si pgcd(a;b)1, alors pgcd(a;b)dpgcd(a;b)d

Exercice 1 Déterminer le PGCD de 8870 et de 3120. Réponse :on utilise l"algorithmed"Euclide : on trouve un PGCD égal à 10. Exercice 2 Écrire l"algorithmed"Euclide pour une calculatrice.

Solution:

- Entreraetb - Tant queb0 (début de la boucle) -E?aquotesdbs_dbs2.pdfusesText_2

[PDF] PGCD et PPCM de deux entiers :

PGCD et PPCM de deux entiers :

Table des matières

I Plus grand commun diviseur de deux entiers :

Définition :

Casparticuliers :

Propriété :

Démonstration ::

Exemple :cherchons le PGCD de 700 et de 90.

TABLE DES MATIÈRES

Propriété :

1. Siadiviseb, alors pgcd(a;b)a

Alors :D(a)D(b)D(b)D(r) et pgcd(a;b)=pgcd(b;r).

Démonstration ::

1. Siadiviseb, tout diviseur deaest un diviseur deb. Par conséquent :D(a)D(b)D(a) et le plus grand

élément deD(a) esta.

2. Pourdémontrerl"égalitédesdeuxensemblesED(a)D(b) etFD(b)D(r), onmontrequeEestinclus

On a : 1960235172et 34300225273.

On en déduit que PGCD(1960 ; 34300)225172980

PGCD(B; 11)11 si et seulement si 11 diviseB.

PGCD(B; 11)11B0(11)n50(11)n5(11).

Exercice 3 Égalité de deux PGCD :

3a2b2(ab)adonc pgcd(4a3b; 3a2b)=pgcd(ab;a)=pgcd(a;b)=pgcd(a;b).

On en déduit que : pgcd(x;y)=pgcd(a;b).

Page 2/

TABLE DES MATIÈRES

5b)5(4a3b)a. Puisqueddiviseaetb, il divise leur PGCDd.

Description de l"algorithme d"Euclide

Soientaetbdeux entiers naturels non nuls, avecab.

On diviseaparb.abq1r1, avec 0r1b.

Sir10, alors pgcd(a;b)bpuisquebdivisea.

On a :br1q2r2, avec 0r2r1.

Sir20, alors pgcd(a;b)=pgcd(b;r1)r1.

Sir20, pgcd(b;r1)=pgcd(r1;r2).

Propriété :

Corollaires :

1. L"ensemble des diviseurs communs à deux entiersaetbest l"ensemble des diviseurs de leur PGCD.

2. Soitaetbdeux entiers non nuls. Sikest un entier naturel non nul, pgcd (ka;kb)kpgcd (a;b).

Démonstration :

1.D(a)D(b)D(b)D(r1)D(r1)D(r2)D(rn)D(0)D(rn)D(d) puisquedrn.

2. On notedle PGCD deaetbetdcelui dekaetkb.

Page 3/

TABLE DES MATIÈRES

III Entiers premiers entre eux

Définition :

Remarques:

Propriété :

Démonstration::

Si pgcd(a;b)1, alors pgcd(a;b)dpgcd(a;b)d

Solution: