[PDF] Arithmétique dans Z PDF Définition 18 1 1 (

Cours darithmétique

seules solutions sont y = 3 z = 6 et y = 4

Résumé du cours darithmétique

Z∗ = Z {0} (entiers relatifs non nuls). Dans ce qui suit entier est synonyme d'entier relatif. 1 Divisibilité dans Z a) Diviseurs et multiples.

[PDF] Algèbre - Exo7 - Cours de mathématiques

Arithmétique. 45. 1. Division euclidienne et pgcd ... z ∈ on a

Suites : Résumé de cours et méthodes 1 Généralités

On a alors U1 = 3×U0 = 3×2 = 6 (on remplace n par 0 dans le relation de récurrence) . 1) Soit (Un) la suite arithmétique de premier terme U0 = 2 et de raison ...

Chapitre4 : Arithmétique dans Z

Mais afin de conserver la généralité des énoncés

COURS DE GÉODÉSIE Chapitre 1 Généralités sur la Géodésie ES1

Il a le même signe que z et Z. Les équations paramétriques de la sphère sont ensemble de méridiens dont les longitudes sont en progression arithmétique et de ...

CHAPITRE 1—LES SUITES NUMÉRIQUES

et u3 = −40. Calculer u6. 5 Exercices d'entrainement. 5.1 Suites numériques - généralités. 1.

Untitled

Module 1: Analyse1 :Suites Numériques et Fonctions (Cours: 24h TD:24h). Responsable: A.EL KASIMI. Module 2: Généralités et Arithmétique dans Z (Cours: 24h

Anneaux et arithmétique

(Sn ◦) est un groupe. 1. Page 6. CHAPITRE 1. GÉNÉRALITÉS SUR LES GROUPES. 1.2 Sous-

Statistiques descriptives et exercices

Calculer le mode Mo et la moyenne arithmétique x. 6. Déterminer à partir du tableau puis à partir du graphe la valeur de la médiane Me. 7. Calculer la variance

Résumé du cours darithmétique

Université Paris-Sud. Résumé du cours d'arithmétique. Les ensembles N et Z. N = {0 1

Algèbre 1 Généralités et Arithmétique dans Z Table des matières

Généralités et Arithmétique dans Z. Table des matières. 1 Logique et ensembles 5 L'anneau Z/nZ et arithmétique modulaire ... (voir cours d'Analyse). Ce.

Untitled

Module 2: Généralités et Arithmétique dans Z (Cours: 24h TD : 24h) Module 6: Informatique 1: Introduction à l'informatique. (Cours: 24h

Filière Licence dEtudes Fondamentales Sciences Mathématiques et

M2 : ALGEBRE 1: Généralités et Arithmétique dans Z. Ch. I. Notions de logique et langage M5 : Physique 2 : Thermodynamique 1 (cours:18 TD:18; TP: 10).

Cours darithmétique

Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él`eves Z ensemble des entiers relatifs. Q ensemble des nombres rationnels.

Projet final de la

Généralités et. Arithmétique dans Z M2 : ALGEBRE 1: Généralités et Arithmétique dans Z ... M5 : Physique 2 : Thermodynamique 1 (cours:18 TD:18; TP: 10).

Arithmétique dans Z

Exercice 6. 1. Montrer que le reste de la division euclidienne par 8 du carré de tout nombre impair est 1. 2. Montrer de même que tout nombre pair vérifie

Anneaux et arithmétique

(Sn ?) est un groupe. 1. Page 6. CHAPITRE 1. GÉNÉRALITÉS SUR LES GROUPES. 1.2 Sous-

Algèbre - Cours de première année

ARITHMÉTIQUE. 2. THÉORÈME DE BÉZOUT. 49. Ainsi pour u = 6 et v = ?29 alors 600 × 6 + 124 × (?29) = 4. Remarque. • Soignez vos calculs et leur présentation

A - GENERALITES SUR LES MOUVEMENTS RECTILIGNES

GENERALITES SUR LES MOUVEMENTS RECTILIGNES reste constant au cours du temps. ... progression arithmétique de raison r le mouvement rectiligne est ...

Cours dalgèbre 1: Généralités et Arithmétique - SMIA S1 PDF

Télécharger cours bien détaillé de module ALGEBRE 1 : Généralités et Arithmétique dans Z (Notions de logiqueThéorie des ensemblesRelations binaires et

Cours Algèbre 1 Généralités et Arithmétique dans Z PDF Gratuit

Cours complet d'Algèbre 1 Généralités et Arithmétique dans Z PDF gratuit + Exercices corrigés et examens Licence / Bachelor Math App

[PDF] Algèbre 1 Généralités et Arithmétique dans Z Table des matières

Généralités et Arithmétique dans Z Table des matières 1 Logique et ensembles 5 L'anneau Z/nZ et arithmétique modulaire (voir cours d'Analyse) Ce

[PDF] Cours darithmétique

Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él`eves pré- parant les olympiades internationales de mathématiques

[PDF] Résumé du cours darithmétique

Université Paris-Sud Résumé du cours d'arithmétique Les ensembles N et Z N = {0 1 2 3 } est l'ensemble des entiers naturels (entiers positifs)

TD 1-2017 - 18 - Algebre 1 Généralités Et Arithmétique Dans Z

TD 1-2017 - 18 - Algebre 1 Généralités Et Arithmétique Dans Z Téléchargez comme PDF TXT ou lisez en ligne sur Scribd Mon Cours Sup amenzou

[PDF] Chapitre4 : Arithmétique dans Z - Melusine

Mais afin de conserver la généralité des énoncés nous n'allons pas pour le cours nous limiter aux entiers positifs A) PGCD et algorithme d'Euclide Étant

[PDF] Arithmétique dans Z

Définition 18 1 1 (Divisibilité diviseur multiple) • Soit a et b deux entiers relatifs b = 0 On dit que b divise a et on écrit b a si et seulement

Arithmétique dans z Cours pdf

Mais afin de conserver la généralité des énoncés nous n'allons pas pour le cours nous limiter aux entiers positifs A) PGCD et algorithme d'Euclide Étant

[PDF] ALGÈBRE ET ARITHMÉTIQUE 1 - Université de Rennes

Du côté arithmétique il contient de nombreux résultats qui seront étudiés dans ce cours: la division euclidienne un algorithme de calcul de pgcd

Abdelmalek Essaadi

Arithmétique dans Z

Fili`ere :

Ann´ee : 2020-2021

Professeur:Younes ABOUELHANOUNE

IDivisibilité,nombres premiers

I.1Notionde divisibilité

Définition18.1.1(Divisibilité,diviseur,m u l t i p l e ) Soitaetbdeuxentiersrelatifs,b?=0.Onditquebdivisea,etonécritb|a,sietseulement s"il existeq?Ztelquea=bq. Ondit dansce casquebestundiviseurdea,etqueaestunmultipledeb.

Onnotea|bpourdirequeadiviseb.

Ainsi,2|4,-2|4,2|-4,et-2|-4.

Soitaetbdeuxentiersp o s i t i f s ,a?=0.Al or sa|bsietseulement sibZ?aZ. Onditquedeuxentiersaetbsontassociéssietseulement sia|betb|a,c"est-à-direaZ=bZ. L e sentiersaetbsontassociéssietseulement siilexisteε?{-1,1}telquea=εb.

Remarque18.1.5

Cerésultatpeutsemblertrivialetsansintérêt.Save r s i o nplusgénérale,pourunanneauintègre

A,estplusintéressante,etaffirmequelesélémentsassociésdiffèrentd"uneconstantem u t l i p l i c a t i v e

appartenant au groupeA?desinversiblesdeA.

P a rexemple,dansK[X],lesélémentsassociésàunpolynômePsonttouslesλP,pourλ?K?.

DansZ[i](entiersdeGauss),lesélémentsassociésàun nombrezsontles4élémentsz,-z,izet

-iz.

Lesélémentsassociésdexsontlesélémentsquijouissentdesmêmespropriétés de divisibilitéquex.

Soit(a,b)?Z2,b?=0.

Ilexisteun uniquec o u p l e(q,r)?Z×Ntelque: a=bq+ret0?r <|b|. L"entierqestappeléquotientdeladivisioneuclidiennedeap a rb. L"entierrestappelér e s t edeladivisioneuclidiennedeap a rb.

Remarquezquebpeutêtrenégatif.

Exemples18.1.7

1.27= 6×4 + 3 = 6×3 + 9 = 6×6-3.

Ainsi,desidentitésa=bq+r,ilyenabeaucoup,maisuneseulevé r i fi elaconditionimposéesur r.Ici,lequotientdeladivision de27par6est4,etsonresteest3.

IDivisibilité,nombrespremiers

2.27=(-6)×(-4)+ 3 =(-6)×(-5)-3.

Sanslav a l e u rabsoluedanslaconditionsurr,c"estladeuxièmeégalitéquiauraitétélabonne.

Maislav a l e u rabsolueimposeunrestepositif.Ainsi,lequotientdeladivision de27par-6est -4,etleresteest3

3.-27= 6×(-4)-3 = 6×(-5)+3.

Ici,onvo i tquesionc h a n g elesignedu nombre divisé,lequotientn"est passimplementl"opposé (attention,celanecorrespondpasàlaplupart desimplémentations informatiquesdeladivision -27par6est-5,leresteest3. Remarquezquelasituationestlamêmequepourlapartieentière,pourlaquelle?-x? ?=-?x?, sauflorsquexest entier.C"estnormale, puisquelapartieentièren"estautrequelequotientde ladivisioneuclidienne(réelle)par1.

4.-27=(-6)×5 +3.

Laplupart des propriétésarithmétiquesdeZ(pourne pas diretoutes)découlent del"existencedecette

divisioneuclidienne.Onpeutdéfinir defaçonsimilairedanscertainsanneauxune divisioneuclidienne, laconditionsurleresteétantunpeuplus dureàexprimer.Onparle dansce casd"anneaueuclidien.

Définition18.1.8(Anneaueuclidien,HP)

SoitAunanneau.OnditqueAest euclidiens"ilestintègre,etm u n id"unstathme,c"est-à-dired"une applicationv:A\{0} →Ntelleque: ?a?A,?b?A\{0},?(q,r)2?A,a=bq+ret(r= 0ouv(r)Exemple18.1.9 OnpeutmontrerqueZ[i]est euclidien,destathmez?→ |z|2.

Ainsi,ZetR[X]sontdesanneauxeuclidiens.Cettedernière propriété nouspermettrad"établir uncertain

nombre de propriétésarithmétiquespourlespolynômes,trèssimilairesàcellesqu"onapourlesentiers.

Remarques18.1.10

Certainsauteursappellentpréstathmelanotion destathmetellequenousl"avonsdéfinie.Ilsimposent uneconditionsupplémentairepourlesstathmes.Ladifférence n"est pastropgênantedanslamesure où onpeutmontrerqu"avecleurterminologie, toutanneauintègrem u n id"un préstathmepeutaussi

êtrem u n id"unstathme.

Danslanotiongénéralede divisioneuclidiennedéfinie parstathme,onn"impose pas de propriété

d"unicité.P a rexemple,dansZ[i],onn"a pas de propriété d"unicité.

Note Historique18.1.11

Ladivisioneuclidienne estappelée ainsiparréférenceàEuclidequidécrit danssesélémentsleprocédéalgo-

rithmiquedesoustractionsrépétéespermettantd"obtenirlequotientetlereste.Cependant,ontrouve tracede

C"estGausslepremier,a v e cl"étudedeZ[i],quiremarquequede nombreuses propriétésarithmétiquesnesont

passpécifiquesàZetdécoulent defaçonplusgénéraledel"existenced"une divisioneuclidiennedans unanneau.

Cetteremarqueest évidemmentàlabase delanotion d"anneaueuclidien.

I.2Congruences

Defaçonquasi-indissociabledelanotion de divisioneuclidienne,nous définissons: Soitn?N?,et(a,b)?Z2.Onditqueaetbsontc o n g r u smodulon,etonécrita≡b[n],siet seulement sindiviseb-a,ouencoresilesdivisionseuclidiennesdeaetbparnontmêmereste. Ontrouveaussi assezsouventlanotationa≡bmodn,ouunmélangedes2 :a≡b[modn]. Nousrappelonslesrésultatssuivants,quenousavonsdéjàeul"occasionde démontrer.

Théorème18.1.13

L ar e l a t i o ndec o n g r u e n c emodulonestuner e l a t i o nd"équivalence.

Théorème18.1.14

L ar e l a t i o ndec o n g r u e n c emodulonestc o m p a t i b l eavecleproduitetlasomme:soit(a,a?,b,b?)?Z4

telsquea≡a?[n]etb≡b?[n].Al or sa+b≡a?+b?[n]etab≡a?b?[n] End"autreterme,c"estunecongruencesurlesmonoïdes(Z,+)et(Z,×),ausensvudanslec h a p i t r esur lesensembles.

defairelorsd"unesuccessiond"opérations, desréductionsmodulonétapeparétape,plutôtquedetout

calculerdansNetderéduireàlafin.

Exemples18.1.15

Cettepossibilitéderéduirelesopérationsàc h a q u eétapeestégalementimportantpourl"implémentation

explicitementletempsdecalculdesopérationsmodulonpar unréeldépendant denmaisne dépendant pas desopérandes.

I.3Nombrespremiers

Définition18.1.16(Nombrespremiers)

Soitp?N?.Onditquepestun nombre premiersipadmetexactement2diviseurspositifsdistincts (àsavoir1etplui-même) Remarquezquel"existencede deux diviseurs distinctsexclutd"office1del"ensembledes nombres premiers, puisqu"il n"aqu"undiviseur.

IDivisibilité,nombrespremiers

Définition18.1.17(Nombrescomposés)

Soitn?N?.Onditquenestun nombrecomposésinpossèdeaumoins3diviseurspositifsdistincts, ouend"autrestermes,sinpossèdeun diviseurpositifdistinct de1etden.

Proposition18.1.18

T o u tnombrec o m p o s éadmetundiviseurstrictpremier.

Cettepropositionestàlabase del"existencedeladécomposition primaire.L"unicité,quantàelledécoule

decevieuxlemme,dont nous démontronslacontraposéedefaçonélémentaire,par descenteinfinie(cette

démonstrationesttrèsproche decellequ"endonneGauss):

Lemme18.1.19(Euclide)

Soitaetbdeuxentiers etpunentierpremiertelquep|ab.Al or sp|aoup|b. Cettepropriétéseretraduitsurles idéauxparab?pZ=?a?pZoub?pZ,ouencore,dansZ/pZ: ab= 0=?a= 0oub= 0 Ainsi,le lemmed"EuclidetraduitlefaitqueZ/pZestintègre.

Remarque18.1.20

Cettepropriétéestmêmeunecaractérisationdes nombres premiers, puisquesinn"est pas premier etdifférent de1,etsin=abestune décomposition nontriviale,alorsl"égalité ab= 0dansZ/nZ contreditl"intégrité.Ainsin >1estpremiersietseulement siZ/nZestintègre.

Defaçonplusgénéral,étantdonné unanneaucommutatifA,etunidéalI,Iest enparticulier unsous-

groupedistingué deA,etonpeutdonc définir unestructuredegroupequotientsurA/I.Iln"est pas dur

celui-cipasseauquotient.Desvé r i fi c a t i o n simmédiatesmontrentqueA/Iestalorsm u n id"unestructure

d"anneau.C"estparexempleainsiqu"onobtientlastructured"anneau deZ/nZ,parquotientdel"anneau

Définition18.1.21(Idéalpremier,HP)

SoitAunanneaucommutatif, etIunidéaldeA.OnditqueIestunidéalpremier deAsietseulement siA/Iestintègre. Ainsi,dansZ,pestpremiersietseulement sipZestunidéalpremier deZdifférent de{0}etZ(qui sontaussidesidéauxpremiers). Théorème18.1.22(Combiende nombres premiers?)

Il y auneinfinitédenombrespremiers.

C"estbienjolitoutça,maiscommentfairepourdéterminerlesnombres premiers(pas tropgros)?

Erathostène,mathématicien,astronome,bibliothécaireenc h e fd"Alexandrie(excusezdupeu),astéroïde

et cratèrelunaire,réponditàcettequestionily adéjàtrèslongtemps,par un procédé d"élimination.

P o u rtrouver touslesnombres premiersinférieursouégauxàn:

2.Lepluspetitd"eux,àsavoir2,estpremier(iln"a pas de diviseurstrictementpluspetitquelui,

autreque1)

3.Lesm u l t i p l e sstrictsde2nesontpas premiers,onlesbarretous.

4.P a r m ilesnombresrestants(enexcluantlesnombres premiers précédents,àsavoir2dansla

premièreétape, et en excluantlesnombres barrés),lepluspetitestpremier(iln"est divisible par aucunnombre premierstrictementpluspetitqueluietdifférent de1,sinonilseraitbarré).On barretoussesm u l t i p l e sstrictsquinepeuventpasêtrepremiers,etonrecommencecette étape jusqu"àépuisementdetouslesentiersdela liste.

Cetalgorithmeesttrèsfacileàimplémenterdans unlangage informatique.Iln"estévidemment efficace

quepourdespetitesv a l e u r sden,maisnepeutpasserviràlarecherchedetrèsgrandsnombres premiers.

Notamment,ilestàpeuprèsinutilisablepourrépondreàlaquestiondesavoir siuntrèsgrandnombre

commelaméthodeRSA).

IIDécompositionprimaire d"unentier

II.1Décompositionprimaire

T o u tentierstrictementp o s i t i fns"écritdefaçonuniquesouslaforme n=p1× ··· ×pk, oùp1?···?pksontdesnombrespremiers,c eproduitétant éventuellementvidesin=1.

Unanneaudanslequelonaune propriété d"existenceetd"unicité(àfacteursm u l t i p l i c a t i f sinversiblesprès,

etàl"ordreprès desfacteurs)d"une décompositionenfacteursirréductiblesestappeléanneaufactoriel.

Ainsi,quitteàm u l t i p l i e rparl"élément inversible-1pourobtenirladécomposition d"unentierrelatif,ce

estfactoriel.P a railleurstoutanneaueuclidien estprincipal.Donctoutanneaueuclidien estfactoriel. C"estparexemplelecasdeK[X],lorsqueKestuncorps(ainsi toutpolynômesedécompose defaçon

unique,àélémentsinversiblesprès,commeproduit depolynômesirréductibles).C"estparexempleaussi

lecasdel"anneauZ[i]desentiersdeGauss.Laquestionseposealors,notamment danscederniercas,

rapportaveclethéorèmedes deuxcarrés(donnantladescription desentierss"écrivantcommesommede

deuxcarrés).

II.2V a l u a t i o n sp-adique

Unnombre premierppouvantapparaîtreplusieursfoisdansladécomposition den,nous définissons:

Définition18.2.2(Valuationp-adique)

Soitnunentier etpunentierpremier.Onappellev a l u a t i o np-adiquedel"entiernlenombre d"occur- rences(éventuellementn u l )del"entierpdansladécomposition primaire den.

IIDécompositionprimaired"unentier

Ils"agitdonc del"uniqueentiervtelquepvdivisenmaispaspv+1. EnnotantPl"ensembledes nombres premiers,ilvientdonc: Proposition18.2.3(Reexpressiondeladécomposition primaire)

Pourtoutn?N?

n=? p?Pp vp(n), c eproduit ayantunsens,puisquec o n s t i t u éd"unnombre finidetermesnoné g a u xà1. Proposition18.2.4(Règlessurlesv a l u a t i o n s ) Soitaetbdeuxentiersstrictementp o s i t i f s ,etpunnombrepremier.

1.Ona :vp(ab) =vp(a) +vp(b).

2.Sibdivisea,ona :vp?

a b? =vp(b)-vp(a).

Exemples18.2.5

1.Déterminer,pourppremier,vp((p2)!),etplusgénéralementvp((pk)!),puis plusgénéralement

v p(n!)(formuledeLegendre)

2.Déterminervp??n

k?? enfonctiondenetk.

Onobtientenparticulierle:

Lemme18.2.6

Soitpunnombrepremier.Al or sp o u rtoutk?[ [ 1,p-1]],?p k? ≡0[p].

Decelemme,ontire:

Proposition18.2.7

Soitaetbdeuxentiers etpunnombrepremier.Al or s(a+b)p≡ap+bp[p].

l"identitéd"aprèslepetitthéorèmedeF e r m a t ) ,etplusgénéralementsurtoutcorpsdecaractéristiquep.

IlestappelémorphismedeF r o b e n i u s.

Laproposition précédente,ainsiquenousve n o n sdelesuggérer,aunrapporttrèsétroitaveclepetit

théorèmedeF e r m a t .Onpeutenfaitdémontrercedernieràpartir decetteproposition par unerécurrence

assezimmédiate. Théorème18.2.8(Petit théorèmedeF e r m a t ) Soitpunnombrepremier,etx?Z.Al or s:xp≡x[p].

Side plus,x?≡0[p],alorsxp-1≡1[p].

Évidemment,cettepreuveexpliquemoinsbienlaraisonprofonde durésultatquelapreuvevoya ntce résultatcommeuncasparticulier duthéorèmedeLagrange,appliquéau groupe(Z/pZ)?.

Remarque18.2.9

LepetitdethéorèmedeF e r m a testnotammentbeaucouputilisé danslestestsde non primalité(avec

unordinateur!).Eneffet,pourmontrerqu"unentierpn"est pas premier,ilsuffitdetrouverunentier atelqueap?≡a[p].Ainsi,parexemple,àl"aided"unordinateur, onpeuttrouverfacilement,pour n=1

9(1031-1)(nombrecontituéde31c h i ff r e s1)que2n?≡2 [n].Ainsi,nn"est pas premier.T r o u v e r

une décomposition denestuneautrepaire demanches...

Enrevanche,déduire delav a l i d i t édetestsdeF e r m a tqu"unnombreestpremierestbeaucoupplus délicat,

carlepetitthéorèmedeF e r m a tnecaractérisepaslesnombres premiers:ilexistedes nombrescomposés

vé r i fi a ntles identitésduthéorèmedeF e r m a t(lasecondeidentitéétantalorsdonnéepourtoutxpremier

IIIPGCDetPPCM

III.1PGCDetPPCMd"uncoupled"entiers

Lemme18.3.1(Sommede deuxgroupesabéliens)

SoitHetKdeuxsousgroupesd"ungroupeabélien(G,+).Al or sH+Kestleplusp e t i tgroupec o n t e n a n t H?K.

Proposition/Définition18.3.2(PGCD)

Soitaetbdeuxentierspositifstelsquel"unaumoinsdesentiersaetbestnonn u l ,etm?N?.Les propositionssuivantes sontéquivalentes: (i)l"entiermestlemaximum(pourl"ordreusuel) de{d?N?|ddiviseaetddiviseb} (ii)l"entiermestlemaximum(pourl"ordrede divisibilité) de{d?N?|ddiviseaetddiviseb}. (iii)m= inf(N?,|)(a,b) (iv)aZ+bZ=mZ Sil"unedecesquatreconditions équivalentes estsatisfaite,onditquemestleplusgrandc o m m u n

Ainsi,lePGCDdeaetbest entièrement caractériséparl"égalitédesidéaux(ennotant(a)l"idéalengendré

para) : (a) +(b) =(a?b). Remarquezquepourétablir cepointpartant deladescription usuelle(premierpoint),onse sertdufait

quetoutidéaldeZs"écritZ·a,doncqueZestprincipal.LefaitqueZestprincipal nousassureégalement

quelepluspetitidéalcontenantaetbest engendrépar unélément.C"estlàunefaçonde définirlepgcd,

comme élémentgénérateurdel"idéalengendréparaetb. Cettedéfinitionestv a l i d edanstoutanneauprincipal: Définition18.3.3(PGCDdans unanneauprincipal,HP) defaçonuniqueàinversiblesprès par: (d) =(a) +(b).

IIIPGCDetPPCM

Danscertains cas,unc h o i xde pgcds"impose(lepgcdpositifdansZparexemple).Dansce casonpeut utiliser une notation nonambiguë(a?bparexemple), etparler duPGCD.Danslesautrescas,onparle d"UNPGCD,etonnepeututiliser une notationqu"àabusprès. Ainsi,enprenant desrestesdivisionseuclidiennessuccessivesledernierrestenonn u lfourniralePGCD:

Entrée:a,b:entiersnaturels

Sortie:a?b

tantqueb >0faire a,b←b,a%b fintantque renvoyera

Proposition/Définition18.3.4(PPCM)

Soitaetbdeuxentiersnonn u l s ,etM?N?.Lespropositionssuivantes sontéquivalentes: (i)l"entierMestleminimum(pourl"ordreusuel) de{m?N?|adivisemetbdivisem} (ii)l"entierMestleminimum(pourl"ordrede divisibilité) de{m?N?|adivisemetbdivisem} (iii)M=sup(N?,|)(a,b) (iv)MZ=aZ∩bZ. Sil"unedecesquatrepropositionséquivalentes estsatisfaite,onditqueMestleplusp e t i tc o m m u n Encoreunefois,cedernierpointpeutêtrepriscommedéfinition dans unanneauprincipal. Définition18.3.5(PPCMdans unanneauprincipal,HP) SoitAunanneauprincipaletaetbdeuxélémentsnonn u l sdeA.AlorsunPPCMdeaetbestun

élémentmtelque

(m) =(a)∩(b). Cequiestparfoisévidentsurles idéauxnel"estpastoujoursautantpourlesautresdescriptions: Proposition18.3.6(Distributivitédu produitsur?et?) Soitaetbdeuxentiersnaturels,etcunentiernaturel non nul.

1.Siaetbnesontp a stouslesdeuxnuls,(a?b)·c=(ac)?(bc).

2.Siaetbsontnon nuls,(a?b)·c=(ac)?(bc).

III.2IdentitédeBézout

L"identitédeBézoutest elleaussiuneconséquenceimmédiatedelacaractérisationparles idéaux:

1.Soitaetbdeuxentiersdontl"unaumoinsestnon nul.Al or silexistedesentiersr e l a t i f sxety

telsqueax+by=a?b.

2.R é c i p r o q u e m e n t ,étantdonnéunentierd?N?,s"ilexistedesentiersr e l a t i f sxetytelsque

d=ax+by, alorsa?b|d.

Note Historique18.3.8

•C"estlenom d"ÉtienneBézout,mathématicienfrançaisdu18esiècle,quiestleplussouventassociéàce

résultat.C"estpourtantàClaude-GaspardBachetdeMéziriacquel"ondoitlapremière preuve, parue dans

sonouvrageProblèmesplaisansetdélectablesquisefontp a rlesnombres,paruen1624.Sa preuveestcelle quenous présentonsci-dessous(parl"algorithmed"Euclide)

•Qu"afaitBézoutalorspoura v o i rdroitàtousceshonneurs?Ilagénéralisélerésultatàd"autressituations,

notammentaucasdespolynômes.

•Ilestintéressantde noterquelefameuxouvragedanslequelF e r m a técrivitdans unemargequ"ilsavait

démontrercequ"onappelle aujourd"huilethéorèmedeF e r m a t - W i l e sest enfaitunetraductionparBachet

deMériziacdel"A r i t h m é t i q u edeDiophante.Le mondeestpetit...

Ladémonstration passant parles idéauxpeutsegénéraliserdans unanneauprincipal.Ellepossède

l"inconvénientde ne pasêtre constructive.Ilpeutêtreintéressantdetrouverexplicitementdesentiersx

déterminera?b,etd"obtenir uneidentitédeBézout:ils"agitdel"algorithmed"Euclide.Ilestintéressant

de noterquecetalgorithmeestv a l i d eàpartir dumomentoùl"ondispose d"une notion de division Ainsi,parexemple,ilnouspermettrad"obtenir desidentitésdeBézoutdansR[X].

Lemme18.3.9

Soitaetbdeuxentiersp o s i t i f s ,b?=0.Soitrler e s t edeladivisioneuclidiennedeap a rb.Al or s a?b=b?r. Soitaetbdeuxentiersp o s i t i f s ,b?=0.Eneffectuantladivisioneuclidiennedeap a rb,puisen

effectuantladivisioneuclidiennedebp a rler e s t eobtenue,et enc o n t i n u a n tainsiendivisantl"ancien

r e s t ep a rlenouveaur e s t e ,onfinitp a robtenirunr e s t enul. L edernierr e s t enon nulestalorsé g a lauPGCDdeaetdeb.

L"identitédeladivisioneuclidiennep e r m e talors d"écrire,étapep a rétape,lesr e s t e ssuccessifsc o m m e

c o m b i n a i s o nlinéairedeaetbàc o e ffi c i e n t sdansZ.L adernièreétapefournituneidentitéde Bézout.

Ainsi,en écrivantr0=a,r1=bpuislesdivisionseuclidiennessuccessives: ?r

0=r1q2+r2

1=r2q3+r3

rk-2=rk-1qk+rk r k-1=rkqk+1+rk+1, avecr2?=0,r3?=0,...,rk?= 0etrk+1=0,onark=a?b.Deplus,enposantx0=1,x1=0,y0=0, y

1= 1etpourtouti?[ [ 3,k] ]

x i=xi-2-qixi-1etyi=yi-2-qiyi-1, on obtientpourtouti?[ [ 1,n] ], r i=axi+byi, doncenparticulierpouri=k,on obtientuneidentitédeBézout: a?b=axk+byk. Onpeutdonc décrire defaçonplusalgorithmique:

IIIPGCDetPPCM

Entrée:a,b:entiersnaturels nonn u l s

Sortie:m,u,vtelsquem=a?b=ua+bv

u,v,w,x,r ,s←1,0,0,1,a,b; tantques?= 0faire q,s,r←r//s,r%s,s; w,u←u-qw,w; x,v←v-qx,x fintantque renvoyer(r,u,v)

Enpratique,pourne pass"embrouiller,mieuxv a u técrirelesdifférentesrelationsobtenuesparladivision

euclidienne, enremplaçantétapeparétapelesrestesobtenusparleurexpressionobtenuerécursivement

enfonctiondeaetb.

Exemple18.3.11

T r o u v e ràl"aidedel"algorithmed"Euclidelepgcd de27et33,ainsiqu"uneidentitédeBézout. Àretenir:onn"a pas unicité delarelationdeBézout!

III.3PGCDetPPCMd"unefamillefinie d"entiers

Lanotion dePGCDetdePPCMde deuxentierspeutêtregénéraliséeàun plusgrandnombre d"entiers:

Proposition/Définition18.3.12(PGCDd"un nombre fini d"entiers)

Soita1,...,andesentiersnaturels, nontousn u l s ,etmunentiernaturel.Lespropriétéssuivantes sont

équivalents:

(i)mestlemaximum(ausensdel"ordreusuel) desentiersdquidivisentc h a c u ndesai,i?[ [ 1,n] ]. (ii)mestlemaximum(ausensdeladivisibilité) desentiersdquidivisentc h a c u ndesai,i?[ [ 1,n] ]. (iii)m= inf(N?,|)(a1,...,an) (iv)mZ=a1Z+a2Z+···+anZ. Sil"unedecesquatrepropositionséquivalentes estsatisfaite,onditquemestlePGCDdelafamille (a1,...,an)etonnotem=a1?a2? ··· ?an.

Delamêmefaçon:

Proposition/Définition18.3.13(PPCMd"un nombre fini d"entiers) Soita1,...,andesentiersnaturels, nonn u l s ,etmunentiernaturel.Lespropriétéssuivantes sont

équivalents:

(i)mestleminimum(ausensdel"ordreusuel) desentiersmm u l t i p l e sdec h a c u ndesai,i?[ [ 1,n] ].

(ii)mestleminimum(ausensdeladivisibilité) desentiersmm u l t i p l e sdec h a c u ndesai,i?[ [ 1,n] ].

(iii)m=sup(N?,|)(a1,...,an) (iv)mZ=a1Z∩a2Z∩ ··· ∩anZ. Sil"unedecesquatrepropositionséquivalentes estsatisfaite,onditquemestlePPCMdelafamille (a1,...,an)etonnotem=a1?a2? ··· ?an. a

1? ··· ?an=((a1?a2)?...)?aneta1? ··· ?an=((a1?a2)?...)?an.

parles idéaux: Soita1,...,andesentiersnaturels nontousnuls.Al or silexistedesentiersr e l a t i f sx1,...,xntelsque a

1? ··· ?an=x1a1+···+xnan.

R é c i p r o q u e m e n t ,s"ilexistedesentiersx1,...,xntelsque d=x1a1+···+xnan, alorsdestunmultipledea1? ··· ?an.quotesdbs_dbs14.pdfusesText_20

[PDF] [PDF] Arithmétique dans Z Définition 18 1 1 (

Abdelmalek Essaadi

Arithmétique dans Z

Fili`ere :

Ann´ee : 2020-2021

Professeur:Younes ABOUELHANOUNE

IDivisibilité,nombres premiers

I.1Notionde divisibilité

Onnotea|bpourdirequeadiviseb.

Ainsi,2|4,-2|4,2|-4,et-2|-4.

Remarque18.1.5

Soit(a,b)?Z2,b?=0.

Remarquezquebpeutêtrenégatif.

Exemples18.1.7

1.27= 6×4 + 3 = 6×3 + 9 = 6×6-3.

IDivisibilité,nombrespremiers

2.27=(-6)×(-4)+ 3 =(-6)×(-5)-3.

3.-27= 6×(-4)-3 = 6×(-5)+3.

4.-27=(-6)×5 +3.

Définition18.1.8(Anneaueuclidien,HP)

Remarques18.1.10

êtrem u n id"unstathme.

Note Historique18.1.11

I.2Congruences

Théorème18.1.13

Théorème18.1.14

Exemples18.1.15

I.3Nombrespremiers

Définition18.1.16(Nombrespremiers)

IDivisibilité,nombrespremiers

Définition18.1.17(Nombrescomposés)

Proposition18.1.18

Lemme18.1.19(Euclide)

Remarque18.1.20

Définition18.1.21(Idéalpremier,HP)

Il y auneinfinitédenombrespremiers.

2.Lepluspetitd"eux,àsavoir2,estpremier(iln"a pas de diviseurstrictementpluspetitquelui,

3.Lesm u l t i p l e sstrictsde2nesontpas premiers,onlesbarretous.

4.P a r m ilesnombresrestants(enexcluantlesnombres premiers précédents,àsavoir2dansla

IIDécompositionprimaire d"unentier

II.1Décompositionprimaire

II.2V a l u a t i o n sp-adique

Définition18.2.2(Valuationp-adique)

IIDécompositionprimaired"unentier

Pourtoutn?N?

1.Ona :vp(ab) =vp(a) +vp(b).

2.Sibdivisea,ona :vp?

Exemples18.2.5

1.Déterminer,pourppremier,vp((p2)!),etplusgénéralementvp((pk)!),puis plusgénéralement

2.Déterminervp??n

Onobtientenparticulierle:

Lemme18.2.6

Decelemme,ontire:

Proposition18.2.7

IlestappelémorphismedeF r o b e n i u s.

Side plus,x?≡0[p],alorsxp-1≡1[p].

Remarque18.2.9

9(1031-1)(nombrecontituéde31c h i ff r e s1)que2n?≡2 [n].Ainsi,nn"est pas premier.T r o u v e r

IIIPGCDetPPCM

III.1PGCDetPPCMd"uncoupled"entiers

Lemme18.3.1(Sommede deuxgroupesabéliens)

Proposition/Définition18.3.2(PGCD)

IIIPGCDetPPCM

Entrée:a,b:entiersnaturels

Sortie:a?b

Proposition/Définition18.3.4(PPCM)

élémentmtelque

1.Siaetbnesontp a stouslesdeuxnuls,(a?b)·c=(ac)?(bc).

2.Siaetbsontnon nuls,(a?b)·c=(ac)?(bc).

III.2IdentitédeBézout

1.Soitaetbdeuxentiersdontl"unaumoinsestnon nul.Al or silexistedesentiersr e l a t i f sxety

2.R é c i p r o q u e m e n t ,étantdonnéunentierd?N?,s"ilexistedesentiersr e l a t i f sxetytelsque

Note Historique18.3.8

Lemme18.3.9

0=r1q2+r2

1=r2q3+r3

1= 1etpourtouti?[ [ 3,k] ]

IIIPGCDetPPCM

Entrée:a,b:entiersnaturels nonn u l s

Sortie:m,u,vtelsquem=a?b=ua+bv

Side plus,x?≡0[p],alorsxp-1≡1[p].