ARITHMÉTIQUE DES ENTIERS RELATIFS - Christophe Bertault[PDF] exercices arithmétique 3ème
[PDF] cours arithmétique terminale s spécialité
[PDF] arithmétique des nombres entiers capes
[PDF] ensemble des nombres entiers naturels n et notions
[PDF] l'arithmétique dans n tronc commun exercices
[PDF] math tronc commun bac international
[PDF] exercices corrigés maths tronc commun maroc
[PDF] les nombres pairs et impairs tronc commun exercice
[PDF] l ensemble n et les notions d arithmétique
[PDF] exercices de maths tronc commun science en francai
[PDF] les ensembles n z q r tronc commun exercices
[PDF] l arithmétique dans n tronc commun exercices corri
[PDF] ensemble des nombres entiers naturels n et notions
[PDF] l'arithmétique dans n exercices corrigés
Chapitre 10ArithmétiqueSommaireI Divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .951) La propriété fondamentale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .952) La division euclidienne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .963) Congruences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .964) Diviseurs communs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .96II Éléments premiers entre eux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .971) Théorème de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .972) Conséquences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98III Le plus grand diviseur commun. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .981) Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .982) Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .993) Généralisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .100IV Le plus petit multiple commun. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1011) Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1012) Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101V Nombres premiers, décomposition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1021) Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1022) Décomposition en facteurs premiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1033) Notion de valuationp-adique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1034) Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104VI Solution des exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .105I DIVISIBILITÉ1) La propriété fondamentaleToute partie deZnon vide et minorée admet un plus petit élément.Théorème 10.1Preuve: SoitAune partie deZnon vide et minorée par un entiern0. SoitMl"ensemble des minorants deA, on an02M,supposons quen2MAE)nÅ12M, alors d"après le principe de récurrence,8n2Z,n>n0AE)n2M. Soitp2A,p>n0, doncpÅ12Mce qui entraîne quepÅ16p: absurde, donc il existe un entiern1tel quen12Metn1Å1ÝM,mais alors il existe un élémentp1deAtel quep1Çn1Å1, d"oùn16p1Çn1Å1, ce qui entraînep1AEn1, et doncn12A,nécessairementn1est le plus petit élément de A.²Toute partie non vide et majorée deZadmet un plus grand élément. En effet, siAest non videmajorée, alors¡AAE{¡a/a2A}est non vide minorée, donc¡Aadmet un plus petit élément¡n0, cequi signifie quen0est le plus grand élément de A.²Toute partie non vide deNadmet un plus petit élément (propriété fondamentale deN).À retenirMPSI3 (2018-19) LYCÉEMONTAIGNE- 95 -©Fradin Patrick -
Éléments premiers entre eux Chapitre 10 : ArithmétiquePoura2Z, on noteDal"ensemble des diviseurs dea. Sia,b2Z, on noteDa,bl"ensemble des diviseurscommuns àaetb, on a doncDa,bAEDa\Db, cet ensemble contient toujours§1.Définition 10.3(diviseurs communs)Remarque 10.2 --Pour tout élément a2Z,§1ja.-Si a6AE0, alorsDaest un ensemble fini, plus précisémentDa½J¡jaj;jajK.-D0AEZ,D§1AE{§1}.-Si a et b sont dansZ:DaAEDjaj(on en déduit queDa,bAEDjaj,jbj).Soienta,b,q,r2Z, siaAEbqÅr, alorsDa,bAEDb,r.Théorème 10.6Preuve: Sid2Da,b, alorsdjaetdjbdoncdja¡bq i.e. djr, doncd2Db,r.Réciproquement, sid2Db,r, alorsdjbetdjrdoncdjbqÅr i.e. dja, d"oùd2Da,b.Application -Le théorème ci-dessus fournit un algorithme pour la recherche des diviseurs communs àaetb(entiersnaturels) basé sur la division euclidienne : c"estl"algorithme d"Euclide1, voici son principe :On remarque que sibAE0 alorsDa,bAEDa. On peut supposer désormais queb6AE0 et on cherche à calculerDAEDa,b:Étape 1: on effectue la division euclidienne deaparb,aAEbq1År1avec 06r1Çb. On aDAEDb,r1, doncsir1AE0 alors DAEDb, sinon on passe :Étape 2: on effectue la division euclidienne debparr1,bAEr1q2År2avec 06r2Çr1. On aDAEDr1,r2,donc sir2AE0 alors DAEDr1, sinon on passe :Étape 3: on effectue la division euclidienne der1parr2;r1AEr2q3År3avec 06r3Çr2. On aDAEDr2,r3,donc sir3AE0 alors DAEDr2, sinon on passe à l"étape 4...La suite des restes obtenus est une suite strictement décroissante d"entiers positifs, elle est donc néces-sairement finie,i.e.il existe un entiern>1 tel quernAE0, l"ensemble cherché est doncDAEDrn¡1(avec laconventionr0AEb).Da,bAEDroùrest le dernier reste non nul dans l"algorithme d"Euclide.À retenirZExemple: Cherchons les diviseurs communs àaAE336 etbAE210- on effectue la division deaparb: 336AE1£210Å126, donc Da,bAED210,126.- on effectue la division de 210 par 126 : 210AE1£126Å84, donc Da,bAED210,126AED126,84.- on effectue la division de 126 par 84 : 126AE1£84Å42, donc Da,bAED84,42.- on effectue la division de 84 par 42 : 84AE2£42Å0, donc Da,bAED42,0AED42, c"est à dire :D336,210AE{§1,§2,§3,§6,§7,§14,§21,§42}.II ÉLÉMENTS PREMIERS ENTRE EUX1) Théorème de BézoutSoienta,b2Z, on dit queaetbsont premiers entre eux (ouaest premier avecb) lorsque le seuldiviseur commun positif est1,i.e.Da,bAE{§1}.Définition 10.41.EUCLIDE(300 av. J.C. - 275 av. J.C. environ) : on ne sait pratiquement rien de sa vie, il était vraisemblablement grec. Sonoeuvre est colossale et son ouvrage fondamental "Les éléments» regroupe toutes les connaissances de l"époque, il faudra près devingt siècles pour dépasser son oeuvre.MPSI3 (2018-19) LYCÉEMONTAIGNE- 97 -©Fradin Patrick -
Le plus grand diviseur commun Chapitre 10 : ArithmétiqueRemarque 10.3 --Dire queaest premier avecbrevient à dire que le dernier reste non nul dans l"algorithme d"Euclideest1.-Siaest premier avecb, alors au moins un des deux est non nul (sinon l"ensemble des diviseurs communsestZ).-a est premier avec a si et seulement si a§1.Soienta,b2Z, alorsaetbsont premiers entre eux si et seulement si il existeu,v2Ztels queauÅbvAE1. Les entiersuetvsont appelés coefficients de Bézout (non uniques en général).Théorème 10.7(théorème deBézout2)Preuve: Supposons queuetvexistent et soitdun diviseur commun àaetb, alorsdjaetdjb, doncdjauÅbvi.e.dj1, doncdAE§1 ce qui prouve queaetbsont premiers entre eux.Réciproquement : siaest premier avecb. En appliquant l"algorithme d"Euclideon vérifie qu"à chaque étape leresterkpeut se mettre sous la formerkAEaukÅbvkavecuketvkdansZ(récurrence) (algorithme d"Euclide étendu),comme le dernier reste non nul est 1, il existe bienuetvdansZtels que 1AEauÅbv(de plus on sait les calculer!).ZExemple:8n2Z,netnÅ1 sont premiers entre eux, puisquenÅ1¡nAE1.2) ConséquencesSiaest premier avecbet siaest premier avecc, alorsaest premier avec le produitbc. On en déduitque siaest premier avecc1,...,cn, alorsaest premier avec le produitc1£...£cn.Théorème 10.8Preuve: Il existeu,v2Ztels queauÅbvAE1, il existep,q2Ztels queapÅcqAE1. On effectue le produit de ces deuxrelations, ce qui donnea(ucqÅuapÅpbv)Åbc(vq)AE1, d"après le théorème deBézout,aetbcsont premiers entreeux. Une simple récurrence surnpermet de démontrer la généralisation.Siaest premier avecc, siajbet sicjb, alorsacjb.Théorème 10.9Preuve: Il existeu,v2Ztels queauÅcvAE1, on multiplie parb, ce qui donne :bauÅbcvAEb, orcjbdoncacjbau, etajbdoncacjbcv, ce qui entraîneacjbauÅbcv i.e. acjb.Remarquons que ce théorème est faux lorsqueaetcne sont pas premiers entre eux, par exemple : 2j12 et 4j12mais 2£4AE86j12.Siajbcet siaest premier avecc, alorsajb.Théorème 10.10(théorème deGauss)Preuve:Ilexisteu,v2ZtelsqueauÅcvAE1,onmultiplieparb,cequidonnebauÅbvcAEb,orajbcdoncajbauÅbcv,i.e. ajb.FExercice10.1Résoudre dansZl"équation17xÅ12yAE3.III LE PLUS GRAND DIVISEUR COMMUN1) DéfinitionSoienta,b2Znon tous deux nuls (i.e.a6AE0 oub6AE0), on sait queDa,bAEDroùrest le dernier reste nonnul dans l"algorithme d"Euclide, on voit que les diviseurs communs àaetbont une valeur absolue inférieureou égale à celle deret doncrest le plus grand diviseur commun.Soienta,b2Znon tous deux nuls, on appelle pgcd deaet deble plus grand diviseur commun.Notation :pgcd(a,b)oua^b, c"est le dernier reste non nul dans l"algorithme d"Euclide.Définition 10.52.BÉZOUT Étienne(1730 - 1783) : mathématicien français, l"un des précurseurs de la géométrie algébrique.MPSI3 (2018-19) LYCÉEMONTAIGNE- 98 -©Fradin Patrick -
Nombres premiers, décomposition Chapitre 10 : Arithmétique8n,m2Z, on a :a)8p2P,vp(nm)AEvp(n)Åvp(m).b)8p2P,vp(nÅm)>min(vp(n);vp(m)).c)njm() 8p2P,vp(n)6vp(m).d)Sinetmsont non nuls alors8p2P:vp(n^m)AEmin(vp(n);vp(m))etvp(n_m)AEmax(vp(n);vp(m)).Théorème 10.24(Propriétés)Preuve:a)Si un des deux est nul, c"est évident. Supposonsnetmnon nuls, soitnAEpkqavecp^qAE1 etmAEpk0q0avecp^q0AE1, d"oùnmAEpkÅk0qq0etp^(qq0)AE1, doncvp(nm)AEkk0.b)Si un des deux est nul, c"est évident. Supposonsnetmnon nuls, et avec les mêmes notations, supposonsk6k0,alorsnÅmAEpk[qÅpk0¡kq0] doncvp(nÅm)>k. On remarque qu"il y a égalité lorsquek6AEk0.c)SimAE0 c"est évident, supposonsm6AE0 etnjm, alors pour tout premierp,©k2N/pkjnª½©k2N/pkjmªdoncvp(n)6vp(m). La réciproque est évidente.d)SoitdAEn^malorsvp(d)6vp(n)etvp(d)6vp(m),doncvp(d)6min(vp(n);vp(m)).D"autrepartpmin(vp(n);vp(m))divisenetmdonc divisedd"oùmin(vp(n);vp(m))6vp(d), par conséquentmin(vp(n);vp(m))AEvp(d). Pourle ppcm on peut utiliser le fait que (n^m)(n_m)AE jnmjet doncvp(n_m)AEvp(nm)¡vp(n^m)AEvp(n)Åvp(m)¡min(vp(n);vp(m))AEmax(vp(n);vp(m)).Il découle du théorème ci-dessus que :pgcd(n,m)AEQp2Ppmin(vp(n);vp(m))et ppcm(n,m)AEQp2Ppmax(vp(n);vp(m)).À retenir: formules du pgcd et du ppcmFExercice10.4Soientnetmdeux naturels non nuls, premiers entre eux, tels que le produitnmest un carré, montrer quen et m sont des carrés.4) Applications-Sin6AE §1, alors la décomposition denen produit de facteurs premiers permet de trouver tous lesdiviseurs den.En effet : SinAE¸£p®11£...£p®rr, soitdest un diviseur positif den, sipest un diviseur premier ded,alorspest un diviseur premier den, doncp2{p1,...,pr}, doncds"écrit sous la forme :dAEp¯11£...£p¯rravec 06¯k6®k-Sin,mÝ{¡1;1}, alors à partir de leur décomposition en produit de facteurs premiers, on peut calculerpgcd(n,m)AEQp2Ppmin(vp(n);vp(m))etppcm(n,m)AEQp2Ppmax(vp(n);vp(m)). Plus précisément : SinAE¸£p®11£...£p®rretmAE¹£q¯11£...£q¯ss,alorslesdiviseurspremierscommunsànetmdoiventappartenirà {p1,...,pr}\{q1,...,qs}, d"où la discussion :²{p1,...,pr}\{q1,...,qs}AE?, alorsnetmsont premiers entre eux,i.e.pgcd(n,m)AE1 et doncppcm(n,m)AEjnmj.²{p1,...,pr}\{q1,...,qs}AE{v1,...,vt}, alors quitte à changer la numérotation, on peut supposer quep1AEq1AEv1,...,ptAEqtAEvtsont les diviseurs premiers communs ànetm.pgcd(n,m)AEvk11£...£vkttaveckiAEmin(®i,¯i) pouri2J1;tK.Et :ppcm(n,m)AEvk11£...£vktt£p®tÅ1tÅ1£...£p®rr£q¯tÅ1tÅ1£...£q¯ssaveckiAEmax(®i,¯i) pouri2J1;tK.ZExemple: 336AE24£3£7 et 420AE22£3£5£7, doncpgcd(336,420)AE22£3£7AE84, etppcm(336,420)AE24£3£5£7.MPSI3 (2018-19) LYCÉEMONTAIGNE- 104 -©Fradin Patrick -
Solution des exercices Chapitre 10 : ArithmétiqueVI SOLUTION DES EXERCICESSolution10.1aAE17et bAE12sont premiers entre eux, appliquons l"algorithme d"Euclide :aAEb£1Å5d"où r1AE5AEa¡bbAEr1£2Å2, d"où r2AE2AEb¡2r1AEb¡2(a¡b)AE¡2aÅ3br1AEr2£2Å1, d"où r3AE1AEr1¡2r2AEa¡bÅ4a¡6bAE5a¡7bOn a ainsi une relation de Bézout entreaetb, on en déduit une solution particulière en multipliant par3:15a¡21bAE3,donc(x0AE15,y0AE¡21)est une solution particulière.L"équation équivaut alors àa(x¡x0)AEb(y0¡y), d"après le théorème deGauss,aetbétant premiers entre eux, on abjx¡x0etajy0¡y, i.e.xAEx0ÅbketyAEy0¡bk0, en reportant dans la relation on voit quekAEk0et donc les solutionssont les couples(x0Åbk,y0¡ak)avec k2Z.Solution10.21/À l"itération0,on aB0AEb2N. Si la boucle ne se termine jamais, alors on a une suiteBide nombres non nuls. Àl"itérationiÅ1, on aAiÅ1AEBietBiÅ1est le reste de la division deAiparBi, on en déduit par récurrence suri, que(Bi)est une suite d"entiers positifs (B0AEb2N) et strictement décroissante carBiÅ1ÇBi, ce qui est absurde, donc laboucle while se termine.2/Montrons l"invariant de boucleP(i) :pgcd(a,b)AEpgcd(Ai,Bi), par récurrence suri, au rang0, on aA0AEaetB0AEb,P(0)est donc vraie. SupposonsP(i)vraie et qu"il y a une itérationiÅ1, doncBi6AE0, à l"itérationiÅ1on aAiÅ1AEBi,etAiAEBiQiÅBiÅ1(division euclidienne deAiparBi), doncpgcd(Ai,Bi)AEpgcd(Bi,BiÅ1)AEpgcd(AiÅ1,BiÅ1), ce quimontreP(iÅ1).3/Soitnle nombre d"itérations, à l"issue de l"itérationn, on apgcd(a,b)AEpgcd(An,Bn)(invariant), et comme il n"y apas d"itérationnÅ1cela signifie queBnAE0, finalementpgcd(a,b)AEpgcd(An,0)AEAn. La valeur de la variableAqui est renvoyée est bien le pgcd cherché.Solution10.31/a´b(moda¡b)d"où an´bn(moda¡b), c"est à dire a¡bjan¡bn.a´¡b(modaÅb)d"oùan´(¡b)n(modaÅb), sinest impair alorsan´¡bn(modaÅb), et doncaÅbjanÅbn.2/SoitNAE2pÅ1un nombre premier, on peut écrirepAE2rqavecqimpair (rest valuation2-adique dep), on a alorsNAE22rqÅ1AE³22r´qÅ1q,qétant impair,Nest divisible par22rÅ1, ce nombre est plus grand que1etNest premier,donc22rÅ1AENAE2pÅ1, ce qui entraîne pAE2r(et donc qAE1).3/SoitNAE2p¡1un nombre premier, soitdun diviseur positif dep, on peut écrirepAEdqavecq2N, on a alorsNAE2dqÅ1AE2dq¡1q, doncNest divisible par2d¡1, orNest premier, donc2d¡1AE1ou bien2d¡1AENAE2p¡1,ce qui entraîne dAE1ou dAEp, donc p est premier.Solution10.4Soitpun nombre premier, commen^mAE1, on avp(n^m)AE0, orvp(n^m)AEmin(vp(n);vp(m)), on adoncvp(n)AE0ouvp(m)AE0, d"autre part,nmétant un carré d"entier,vp(nm)est pair, orvp(nm)AEvp(n)Åvp(m)etune des deux valuations est nulle, donc l"autre est forcément paire. Finalement, pour tout premierp,vp(n)est pair etvp(m)est pair, donc n et m sont des carrés d"entiers.MPSI3 (2018-19) LYCÉEMONTAIGNE- 105 -©Fradin Patrick -
quotesdbs_dbs26.pdfusesText_32