[PDF] PGCD - PPCM Théorèmes de Bézout et de Gauss





Previous PDF Next PDF



LES NOMBRES PREMIERS – PPCM

La multiplication de deux nombres même très grands



PGCD ET NOMBRES PREMIERS

Théorème de Bézout : Soit a et b deux entiers naturels non nuls. a et b sont premiers entre eux si et seulement si



PGCD et PPCM

Combinaisons : Les combinaisons aZ + bZ sont exactement les multiples du PGCD. 1. Page 2. 2 Nombres premiers entre eux. Deux nombres sont premiers entre 



PGCD - PPCM Théorèmes de Bézout et de Gauss

15 ?.?. 2559 Définition 1 : Soit a et b deux entiers relatifs non nuls. ... Il ne faut pas confondre des nombres premiers entre eux et des nombres pre-.



PGCD et PPCM de deux entiers :

On suppose a et b premiers entre eux donc pgcd(a ; b) = 1. L'un des deux nombres est non nul



Remédiation – PGCD et PPCM Plus grand commun diviseur (PGCD)

Une fraction est irréductible si le PGCD de ses termes est 1. On dit alors que leurs termes sont premiers entre eux. Vérification du PGCD de deux nombres. Vrai 



Cours darithmétique

précédents : Exercice : On définit le n-i`eme nombre de Fermat par la formule Fn = 22n + 1. Montrer que les Fn sont deux `a deux premiers entre eux.



PEI Math 1 Module 2 / Feuille nOl/page l

La propriété « le produit du PGCD de deux nombres par leur PPCM est égal au produit des ces a' et b' sont donc deux diviseurs de 36 premiers entre eux.



Untitled

g) Faux car 6 et 12 sont deux nombres non premiers entre eux dont le PPCM vaut 12. h) Vrai



calcul-multiples-et-diviseurs.pdf

Les multiples de deux nombres (ou plus) sont les multiples du ppcm de ces Deux nombres naturels dont le pgcd est 1 sont dits « premiers entre eux ».



[PDF] LES NOMBRES PREMIERS – PPCM - Pierre Lux

La multiplication de deux nombres même très grands n'est pas compliquée : avec du papier Si a et b sont premiers entre eux on a PPCM(a ; b) = a × b



[PDF] ppcmpdf

cherche des multiples communs à deux nombres on peut même si l'énoncé ne demande pas de trouver le plus petit d'entre eux chercher le PPCM des deux 



[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

Définition : Soit a et b deux entiers naturels non nuls On dit que a et b sont premiers entre eux lorsque leur PGCD est égal à 1 Exemple :



[PDF] Nombres premiers pgcd et ppcm - Lycée dAdultes

27 jui 2016 · Nombres premiers pgcd et ppcm 3 3 Nombres premiers entre eux il admet exactement deux diviseurs 1 et lui-même



[PDF] PGCD et PPCM de deux entiers :

Montrer que les nombres 3 920 et 1 089sont premiers entre eux et déterminer des entiers u et v tels que 3920u +1089v = 1 Méthode : on écrit toutes les 



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

Le plus petit des multiples corlmuns à deux nombres a et b s'appelle leur plus petit commun multiple et se note ppcm(ab)



[PDF] PGCD PPCM nombres premiers décomposition en produit de

Quand le PGCD de deux nombres vaut 1 on dit qu'ils sont premiers entre eux Par exemple : • deux nombres premiers distincts sont toujours premiers entre



[PDF] I PGCD et PPCM de deux nombres entiers - My MATHS SPACE

I 3 Nombres premiers entre eux Définition 2 On dit que deux entiers relatifs non nuls a et b sont premiers entre eux lorsque leur PGCD est égal



[PDF] PGCDPPCM nombres premiers entre-eux:

Prop: Tous les diviseurs communs à deux entiers sont les diviseurs de leur PGCD Déf: Deux nombres sont dits premiers entre-eux s'ils ont 1 pour PGCD



PPCM - Maxicours

Quel que soit l'entier naturel p les nombres 9p + 4 et 2p + 1 sont premiers entre eux et leur PPCM est égal à leur produit

  • Comment calculer le PPCM avec les nombres premiers ?

    Le ppcm (plus petit commun multiple), de plusieurs nombres décomposés en facteurs premiers est égal au produit de tous les facteurs premiers communs ou non, chacun d'eux n'est pris qu'une seule fois, avec son exposant le plus grand. 45 = 3?? = 3²?. Le ppcm = 2²?²? = 180.

  • Comment trouver le PPCM de deux nombres ?

    Cette méthode consiste à diviser simultanément les nombres dont on cherche le PPCM par des diviseurs premiers. Le PPCM sera alors le produit de ces diviseurs premiers. Attention, la méthode est légèrement différente de celle présentée pour le PGCD.

  • Quel est le PPCM de 5 et 7 ?

    Exemples. Trouver le PPCM de 5 et 7 : 1.
  • Le PPCM est donné par le rapport du produit des 2 entiers donnés et de leur PGCD. On obtient la formule suivante PPCM (a,b) = a × b ÷ PGCD (a,b). Vous pouvez rechercher le PPCM d'entiers jusqu'à 20 chiffres.
DERNIÈRE IMPRESSION LE15 juillet 2016 à 11:11

PGCD - PPCM

Théorèmes de Bézout et de Gauss

Table des matières

1 Plus grand commun diviseur2

1.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Nombres premiers entre eux. . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Algorithme d"Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Plus petit commun multiple4

3 Théorème de Bézout4

3.1 Égalité de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3.2 Théorème de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3.3 Algorithme de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.4 Corollaire de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4 Le théorème de Gauss7

4.1 Le théorème. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.2 Corollaire du théorème de Gauss. . . . . . . . . . . . . . . . . . . . 8

4.3 Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

PAUL MILAN1TERMINALE S SPÉ

TABLE DES MATIÈRES

1 Plus grand commun diviseur

1.1 Définition

Définition 1 :Soitaetbdeux entiers relatifs non nuls. L"ensemble des diviseurs communs àaetbadmet un plus grand élémentD, appelé plus grand commun diviseur.

On note :D=pgcd(a,b)

Démonstration :Existence

L"ensemble des diviseurs communs àaetbest un ensemble fini car intersection de deux ensembles finis. De plus 1 diviseaetbdonc l"ensemble des diviseurs communs àaetbest non vide. Or tout ensemble fini non vide admet un plus grand élément doncDexiste.

Exemples :

pgcd(24,18) =6 pgcd(60,84) =12 pgcd(150,240) =30

Propriétés :

•Sibdiviseaalors pgcd(a,b) =|b|

•Pour tout entier naturelknon nul, on a : pgcd(ka,kb) =kpgcd(a,b).

1.2 Nombres premiers entre eux

Définition 2 :On dit queaetbsont premiers entre eux si et seulement si pgcd(a,b) =1 Exemple :pgcd(15,8) =1 donc 15 et 8 sont premiers entre eux. ?Il ne faut pas confondre des nombres premiers entre eux et des nombres pre- miers. 15 et 8 ne sont pas premiers et pourtant ils sont premiersentre eux. Par contre deux nombres premiers distincts sont nécessairementpremiers entre eux.

PAUL MILAN2TERMINALE S SPÉ

1. PLUS GRAND COMMUN DIVISEUR

1.3 Algorithme d"Euclide

Théorème 1 :Soitaetbdeux naturels non nuls tels quebne divise pasa. La suite des divisions euclidiennes suivantes finit par s"arrêter.Le dernier reste non nul est alors le pgcd(a,b) aparb a=bq0+r0avecb>r0?0 bparr0b=r0q1+r1avecr0>r1?0 r

0parr1r0=r1q2+r2avecr1>r2?0

r n-2parrn-1rn-2=rn-1qn+rnavecrn-1>rn?0 r n-1parrnrn-1=rnqn+1+0

On a alors pgcd(a,b) =rn.

Démonstration :

•La suite des restes :r0,r1,r2, ...,rnest une suite strictement décroissante dans

Ncarr0>r1>r2>···>rn.

Cette suite est donc finie. Il existe alorsntel quern+1=0.

Montrons que pgcd(a,b) =pgcd(b,r0).

SoitD=pgcd(a,b)etd=pgcd(b,r0).

DdiviseaetbdoncDdivisea-bq0=r0, doncDdivisebetr0donc :D?d ddivisebetr0doncddivisebq0+r0=a, doncddiviseaetbdonc :d?D On déduit de ces deux inégalités queD=d: pgcd(a,b) =pgcd(b,r0)

•De proche en proche, on en déduit que :

pgcd(a,b) =pgcd(b,r0) =···=pgcd(rn-2,rn-1) =pgcd(rn-1,rn) orrndivisern-1, donc pgcd(rn-1,rn) =rn Conclusion : pgcd(a,b) =rn. Le dernier reste non nul est le pgcd.

Exemple :

Calculer le pgcd(4 539,1 958).

On effectue les divisions euclidiennes suivantes :

4 539=1 958×2+623

1 958=623×3+89

623=89×7

Conclusion : pgcd(4 539,1 958) =89

Remarque :Le petit nombre d"étapes montre la performance de cet algorithme. Algorithme :Voici un algorithme d"Euclide que l"on peut proposer pour trou- ver le pgcd de deux nombres. On pourrait éventuellement utiliser l"algorithme de la division euclidienne à l"intérieur du programme, mais pourles besoins de simplicité, on utilisera la partie entière pour trouver le quotient.

PAUL MILAN3TERMINALE S SPÉ

TABLE DES MATIÈRES

Variables:a,b,q,rentiers naturels

Entrées et initialisation

Lirea,b

E(a/b)→q

a-bq→r

Traitement

tant quer?=0faire b→a r→b

E(a/b)→q

a-bq→r fin

Sorties: Afficherb

2 Plus petit commun multiple

Définition 3 :Soitaetbdeux entiers relatifs non nuls. L"ensemble des multiples strictement positifs communs àaet àbadmet un plus petit élémentM, appelé plus petit commun multiple.

On le note :M=ppcm(a,b).

Démonstration :Existence

L"ensemble des multiples strictement positifs àaet àbn"est pas vide. En effet|ab| est un multiple positif deaet deb. Toute partie non vide deNadmet un plus petit élément doncMexiste.

Exemple :

ppcm(18,12) =36 ppcm(24,40) =120 Pour additionner deux fractions, on recherche le dénominateur commun le plus petit qui n"est autre que le ppcm.

Propriétés :

•Sibdiviseaalors ppcm(a,b) =|a|

•Siaetbsont premiers entre eux alors ppcm(a,b) =|ab|

•On a :ab=ppcm(a,b)×pgcd(a,b)

3 Théorème de Bézout

3.1 Égalité de Bézout

Théorème 2 :Soitaetbdeux entiers non nuls etD=pgcd(a,b) Il existe alors un couple(u,v)d"entiers relatifs tels que : au+bv=D

PAUL MILAN4TERMINALE S SPÉ

3. THÉORÈME DE BÉZOUT

Démonstration :

SoitGl"ensemble formé par les entiers naturels strictement positifs dela forme ma+nboùmetnsont des entiers relatifs. Gest une partie deNnon vide : on vérifie facilement que|a|?G. Gadmet donc un plus petit élémentdtel qued=au+bv •D=pgcd(a,b)diviseaetbdoncDdiviseau+bv=det doncD?d

•Montrons queddivisea

Divisonsapard, on a alorsa=dq+ravec 0?r

On isole le reste et on remplacedparau+bv:

r=a-dq=a-auq-bvq=a(1-uq) +b(-vq) Doncr=0. En effet sir?=0 alorsr?G, orr•conclusion :D?detd?DdoncD=d.

Conséquence: Tout diviseur commun àaetbdivise leur pgcd.

3.2 Théorème de Bézout

Théorème 3 :Deux entiers relatifsaetbsont premiers entre euxsi et seulement si, il existe deux entiers relatifsuetvtels que : au+bv=1

ROCDémonstration :

Dans le sens?: Immédiat grâce à l"égalité de Bézout.

Dans le sens?: (réciproquement)

On suppose qu"il existe deux entiersuetvtels que :au+bv=1.

DoncDdivise 1. On a bienD=1.

Exemple :: Montrer que(2n+1)et(3n+2)sont premiers entre eux?n?N. Il s"agit de trouver des coefficientsuetvpour queu(2n+1) +v(3n+2) =1. -3(2n+1) +2(3n+2) =-6n-3+6n+4=1 ?n?N, il existeu=-3 etv=2 tel queu(2n+1) +v(3n+2) =1.

Les entiers(2n+1)et(3n+2)sont premiers entre eux.

Exemple :Montrer que 59 et 27 sont premiers entre eux puis déterminer un couple(x,y)tel que : 59x+27y=1 Pour montrer que 59 et 27 sont premiers entre eux on effectue l"algorithme d"Eu- clide et pour déterminer un couple(x,y), on remonte l"algorithme d"Euclide :

PAUL MILAN5TERMINALE S SPÉ

TABLE DES MATIÈRES

59=27×2+5(1)

27=5×5+2(2)

5=2×2+1(3)

59 et 27 sont premiers entre eux.

On remonte l"algorithme d"Euclide :

2×2=5-1

On multiplie l"égalité (2) par 227×2=5×10+2×2

27×2=5×10+5-1

27×2=5×11-1

5×11=27×2+1

on multiplie l"égalité (1) par 11

59×11=27×22+5×11

59×11=27×22+27×2+1

59×11=27×24+1

On a donc : 59×11+27×(-24) =1

3.3 Algorithme de Bézout

Il s"agit de déterminer un couple(u;v)

d"entiers relatifs sachant que les entiers aetbsont premiers entre eux. On doit donc avoir :au+bv=1

On isole le premier terme :

au=b(-v) +r

On teste, en incrémentantu, le reste de

la division dem=auparb. Tant que le reste est différent de 1, on réitère la division.

Onanalyseradeplussileréelbestposi-

tif ou non pour déterminer le quotient.

Une foisutrouvé, on déterminev:

v=1-m bOn teste ce programme avec :a=59 et b=27

On trouve alors :u=11 etv=-24

Variables:a,b,u,v,m,rentiers

Entrées et initialisation

Lirea,b

0→r

0→u

Traitement

tant quer?=1faire u+1→u au→m sib>0alors m-E?mb?

×b→r

sinon m-E?mb+1?

×b→r

fin fin 1-m b→v

Sorties: Afficheruetv

3.4 Corollaire de Bézout

Théorème 4 :L"équationax+by=cadmet des solutions entières si et seulement sicest un multiple du pgcd(a,b).

Démonstration :

Dans le sens?

ax+by=cadmet une solution(x0,y0).

CommeD=pgcd(a,b)diviseaetbil diviseax0+by0.

Ddivise doncc

Dans le sens?(réciproquement)

cest un multiple deD=pgcd(a,b).

Donc il existe un entier relatifktel que :c=kd

PAUL MILAN6TERMINALE S SPÉ

4. LE THÉORÈME DE GAUSS

De l"égalité de Bézout, il existe deux entiers relatifsuetvtels que : au+bv=D

En multipliant park, on obtient :

auk+bvk=kD?a(uk) +b(vk) =c

Donc il existex0=ukety0=vktels queax0+by0=c

Exemple :L"équation 4x+9y=2 admet des solutions car pgcd(4,9) =1 et 2 multiple de 1 L"équation 9x-15y=2 n"admet pas de solution car pgcd(9,15) =3 et 2 non multiple de 3

4 Le théorème de Gauss

4.1 Le théorème

Théorème 5 :Soita,betctrois entiers relatifs non nuls. Siadivise le produitbcet siaetbsont premiers entre eux alorsadivisec. ROCSiadivise le produitbc, alors il existe un entierktel que :bc=ka Siaetbsont premiers entre eux, d"après le théorème de Bézout, il existe deux entiersuetvtels que :au+bv=1

En multipliant parc, on a :

acu+bcv=corbc=ka, donc : acu+kav=c a(cu+kv) =c

Doncadivisec.

Exemple :Trouver les solutions dansZ2de l"équation : 5(x-1) =7y

5 divise 7y, or pgcd(5,7) =1, donc d"après le théorème de Gauss 5 divisey. On

a donc :y=5k

En remplaçant dans l"équation, on a :

5(x-1) =7×5k?x-1=7k?x=7k+1

Les solutions sont donc de la forme :

?x=7k+1 y=5kk?Z

PAUL MILAN7TERMINALE S SPÉ

TABLE DES MATIÈRES

4.2 Corollaire du théorème de Gauss

Théorème 6 :Sibetcdiviseaet sibetcsont premiers entre eux alorsbc divisea. ROCDémonstration :: Sibetcdivisea, alors il existeketk?entiers relatifs tels que : a=kbeta=k?cdonc :kb=k?c bdivisek?c, or pgcd(b,c) =1 donc d"après le théorème de Gaussbdivisek? donc :k?=k??b a=k?c=k??bc

Doncbcdivisea.

Exemple :Si 5 et 12 divisea, comme 5 et 12 sont premiers entre eux, 5×12=60 divisea.

4.3 Propriétés

Ces propriétés découlent du théorème de Bézout et de Gauss. Propriété 1 :Soitaetbdeux entiers non nuls,Dleur pgcd etMleur ppcm. •Il existe deux entiersa?etb?premiers entre eux tels que : a=Da?etb=Db?

•On a les relations suivantes :

M=Da?b?etab=MD

PAUL MILAN8TERMINALE S SPÉ

quotesdbs_dbs41.pdfusesText_41
[PDF] cours developpement communautaire

[PDF] montrer qu'il existe une infinité de nombres premiers de la forme 4n+1

[PDF] extraction du charbon

[PDF] origine du charbon

[PDF] 3 conditions necessaires a la formation du charbon

[PDF] la formation des combustibles fossiles schéma

[PDF] origine des combustibles fossiles seconde

[PDF] formation du charbon schéma

[PDF] somme de racine carré

[PDF] calcul avec racine carré seconde

[PDF] formation du sac embryonnaire chez les spermaphytes

[PDF] formation du grain de pollen pdf

[PDF] fusion partielle et cristallisation fractionnée

[PDF] magmatisme de dorsale

[PDF] taux de fusion partielle