Contrôle de mathématiques
Énoncer puis démontrer le théorème de Gauss. Voir le cours. Exercice 2 de Bezout les entiers naturels n et 2n + 1 sont premiers entre eux.
Exercices pour préparer la composition du premier trimestre 2010
un multiple de 5. 3) Montrer que 2n + 1 et n sont premiers entre eux. 4) a). Déterminer suivant les valeurs de n et en fonction de n le PGCD de a et b.
PGCD ET NOMBRES PREMIERS
On dit que a et b sont premiers entre eux lorsque leur PGCD est égal à 1. Démontrer que pour tout entier naturel n 2n + 3 et 5n + 7 sont premiers entre ...
Exo7 - Exercices de mathématiques
Démontrer en raisonnant par récurrence
Cours darithmétique
Lorsque pgcd(a b) = 1
Exercices de mathématiques - Exo7
Exercice 11 ***IT. Pour n ? N on pose Fn = 22n. +1 (nombres de FERMAT). Montrer que les nombres de Fermat sont deux à deux premiers entre eux. Correction ?.
Corrigé de linterrogation darithmétique
Algorithme d'Euclide entre 128 et 30 : et 14n + 3 sont premiers entre eux. Exercice 4. ... pgcd(a b)=2min(2n
Arithmétique dans Z
1. Montrer que le reste de la division euclidienne par 8 du carré de tout nombre impair est 1. Montrer que pour m = n Fn et Fm sont premiers entre eux.
PGCD - PPCM Théorèmes de Bézout et de Gauss
15 juil. 2016 Exemple : : Montrer que (2n + 1) et (3n + 2) sont premiers entre eux ?n ? N. Il s'agit de trouver des coefficients u et v pour que u(2n + ...
UTM Département de Mathématiques et Informatique Année 2010
Trouver les entiers n ? 1 tels que n ? 1 divise n2 + 1. 3. Montrer que pour Montrer que n et 2n + 1 sont premiers entre eux. 2. On pose a = 2n + 1 et ...
[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques
Démontrer que pour tout entier naturel n 2n + 3 et 5n + 7 sont premiers entre eux D'après le théorème de Bézout avec les coefficients 5 et -2 on peut
[PDF] Ctrle : PGCD PPCM 06 12 2010 - Contrôle de mathématiques
Proposition 1 : Pour tout entier naturel n non nul n et 2n + 1 sont premiers entre eux Proposition vraie : en effet on a (?2)n+(1)(2n+1) = 1 donc d'après
[PDF] Exercices pour préparer la composition du premier trimestre 2010
3) Montrer que 2n + 1 et n sont premiers entre eux 4) a) Déterminer suivant les valeurs de n et en fonction de n le PGCD de a et b On
[PDF] Arithmétique - Exo7 - Exercices de mathématiques
Montrer que l'on peut se ramener au cas où x?y?z = 1 Montrer alors que dans ce cas x y et z sont de plus deux à deux premiers entre eux 2 On suppose
[PDF] chapitre 1 : divisibilité et premiers
Si n ? 2 alors n est un produit de nombres premiers Montrer par une récurrence simple pour tout n ? 1 on a 1 1 · 2 sont premiers entre eux
[PDF] Exo7 - Exercices de mathématiques
17 103 04 Nombres premiers nombres premiers entre eux n(n+1)(2n+1) Démontrer en raisonnant par récurrence que 32n+2 ?2n+1 est divisible par 7
[PDF] Chapitre n°7 : Entiers premiers entre eux - Scolamath
Montrer que 59 et 27 sont premiers entre eux puis déterminer un couple d'entiers relatifs (xy) tels que 59x + 27y = 1
[PDF] Cours darithmétique
Lorsque pgcd(a b) = 1 on dit que a et b sont premiers entre eux Exercice 19* (Nombres de Fermat) Montrer que si 2n + 1 est un nombre premier alors
[PDF] Arithmétique - PCSI 3
13 jan 2023 · Montrer que pour tout n ? 1 n2 divise (n + 1)n ? 1 108 Somme et produit de nombres premiers entre eux Soient a et b deux nombres premiers
[PDF] Chapitre 1 Arithmétique Partie 6 : Nombres premiers entre eux
naturels non nuls et consécutifs est égal à 1 » • Démontrer que si * n?? les entiers n et 2n + 1 sont premiers entre eux
Comment montrer que n et 2n 1 sont premiers entre eux ?
pour montrer que n et 2n+1 sont premiers entre eux, il suffit d'appliquer le théorème de Bézout. a et b sont premiers entre eux, si il existe u et v dans Z tq au+bv=1. ( ie pgcd(a;b)=1). alors on applique ce théorème on a -2).Comment démontrer que deux nombres sont premiers entre eux ?
On dit que a et b sont premiers entre eux lorsque leurs seuls diviseurs communs sont 1 et ?1. Autrement dit, a et b sont premiers entre eux lorsque PGCD(a;b)=1.Comment savoir si deux polynômes sont premiers entre eux ?
On dit que deux polynômes non tous deux nuls sont premiers entre eux si leur PGCD est égal à 1.- Deux nombres entiers sont dits premiers entre eux lorsqu'il n'admette aucun diviseur commun, sinon l'unité. Par exemple 5 et 12 sont premiers entre eux, mais pas 12 et 15 qui admettent 3 comme diviseur commun.
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) =30Proprié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 r0parr1r0=r1q2+r2avecr1>r2?0
r n-2parrn-1rn-2=rn-1qn+rnavecrn-1>rn?0 r n-1parrnrn-1=rnqn+1+0On a alors pgcd(a,b) =rn.
Démonstration :
La suite des restes :r0,r1,r2, ...,rnest une suite strictement décroissante dansNcarr0>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→rTraitement
tant quer?=0faire b→a r→bE(a/b)→q
a-bq→r finSorties: 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=DPAUL 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?dMontrons 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, orrconclusion :D?detd?DdoncD=d.
Conséquence: Tout diviseur commun àaetbdivise leur pgcd. 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, orr3.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=1ROCDé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×227×2=5×10+5-1
27×2=5×11-1
5×11=27×2+1
on multiplie l"égalité (1) par 1159×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=1On isole le premier terme :
au=b(-v) +rOn 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=27On 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→vSorties: 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=DEn multipliant park, on obtient :
auk+bvk=kD?a(uk) +b(vk) =cDonc 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 34 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=1En multipliant parc, on a :
acu+bcv=corbc=ka, donc : acu+kav=c a(cu+kv) =cDoncadivisec.
Exemple :Trouver les solutions dansZ2de l"équation : 5(x-1) =7y5 divise 7y, or pgcd(5,7) =1, donc d"après le théorème de Gauss 5 divisey. On
a donc :y=5kEn 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?ZPAUL 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??bcDoncbcdivisea.
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] on note dn le pgcd de n(n+3) et de (2n+1)
[PDF] pgcd(a^2 b^2)
[PDF] montrer que n et n+1 sont premiers entre eux
[PDF] pgcd*ppcm=ab
[PDF] ppcm de deux nombres premiers entre eux
[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é