MAT231 Chapitre

De
Publié par

MAT231, Chapitre 1 MAT231 – Chapitre 2 : Arithmétique Université Joseph Fourier – 2008-2009 Pierre Bérard Les transparents et les feuilles d'exercices sont disponibles sur 1/22 MAT231, Chapitre 1 Plan du chapitre 2 Chapitre 2, Arithmétique Division euclidienne Plus grand commun diviseur Plus petit commun multiple Nombres premiers Idéaux de Z et Théorème de Bézout Congruences 2/22

  • da ?

  • quotient de la division euclidienne

  • division euclidienne dans z

  • diviseur

  • commun diviseur

  • division euclidienne

  • da

  • z2 unique


Publié le : mardi 19 juin 2012
Lecture(s) : 79
Source : www-fourier.ujf-grenoble.fr
Nombre de pages : 11
Voir plus Voir moins
MAT231, Chapitre 1
MAT231 – Chapitre 2 : Arithmétique Université Joseph Fourier – 2008-2009
Pierre Bérard
Les transparents et les feuilles d’exercices sont disponibles sur http://www-fourier.ujf-grenoble.fr/~pberard
MAT231, Chapitre 1
Plan du chapitre 2
Chapitre 2, Arithmétique Division euclidienne Plus grand commun diviseur Plus petit commun multiple Nombres premiers Idéaux deZet Théorème de Bézout Congruences
1/22
2/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique Division euclidienne
Division euclidienne
Notations :N:=N\ {0},
Z:=Z\ {0}.
Théorème et Définition Pour toutaNet pour toutbN, il existe un couple unique (q,r)tel que a=bq+r,avec 0r<b. Cette écriture s’appelle ladivision euclidiennedeaparb. Le nombreqs’appelle lequotientde la division euclidienne, le nombre rsonreste.
[IAlgorithmes, voir les TD/TP.]
MAT231, Chapitre 1 Chapitre 2, Arithmétique Division euclidienne
3/22
Théorème (Écriture d’un nombre entier en basea) SoitaN,a2. Pour toutxNil existe un développement et un seul de la forme
n n1 x=xna+xn1a+. . .+x1a+x0
avecxiN,0xi<apour toutietxn6=0. Ce développement s’appelle l’écriture dexen baseaet se notex=xnxn1. . .x0ou encorex= (xnxn1. . .x0)aquand on veut spécifier la base de numération.
[IAlgorithmes de conversion, voir les TD/TP.]
4/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique Division euclidienne
Théorème (division euclidienne dansZ) Pour toutaZet pour toutbZ, il existe un couple 2 (q,r)Zunique, tel que
a=bq+ravec 0r<|b|.
[IUtiliser la division euclidienne dansN, voir TD.]
MAT231, Chapitre 1 Chapitre 2, Arithmétique
5/22
Soienta,bdeux entiers non nuls. Définitions On dit queb divise as’il existe un entierqtel quea=bq(le reste de la division euclidienne deaparbest nul). Le nombrebest undiviseurdea. Le nombreaest unmultiplede b.
Notations On noteDal’ensemble des diviseurs deaetDa,bl’ensemble des diviseurs communs àaet àb, c’est-à-dire l’ensembleDa∩ Db.
6/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique
Plus grand commun diviseur
L’ensembleDa∩ Dbn’est pas vide (il contient 1) et il est majoré paraetb. Il admet donc un plus grand élément.
Définition On appelleplus grand commun diviseur(pgcd) deaetbet on notepgcd(a,b)(ou encoreaab) le plus grand élément de Da∩ Db. Plus généralement, lepgcddes nombresa1, . . . ,an, noté pgcd(a, . . . ,a), est le plus grand élément de∩ D. 1nDa1∙ ∙ ∙ ∩an
MAT231, Chapitre 1 Chapitre 2, Arithmétique
Algorithme d’Euclide On définit la suite de nombres entiersr[k]par les relations
r[0] :=a,r[1] :=b
et, pourk0, et tant quer[k+1]est non nul,
r[k+2] :=irem(r[k],r[k+1]),
7/22
le reste de la division euclidienne der[k]parr[k+1]. La suiter[k]atteint 0 à partir d’un certain rang. Le dernier reste non nul estd:=pgcd(a,b).
[IMise en oeuvre de l’algorithme d’Euclide, voir TD.]
8/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique
Théorème (caractérisation dupgcd) Soienta,bdeux entiers non nuls. Soitd:=pgcd(a,b)leurpgcd. 1.L’ensemble des diviseurs communs àaetbest égal à l’ensemble des diviseurs de leurpgcd, c’est-à-direDa,b=Dd. 2.Lepgcddea,best caractérisé comme étant le nombredtel que 0 0 0 0 a=daetb=db,avecpgcd(a,b) =1.
Soienta,b,mtrois entiers non nuls. Alors
MAT231, Chapitre 1 Chapitre 2, Arithmétique
pgcd(ma,mb) =mpgcd(a,b).
Définition Deux entiers non nulsa,bsont ditspremiers entre euxsi leur pgcdest égal à 1. On dit aussi “aest premier avecb”.
9/22
Théorème de Gauss Soienta,b,ctrois entiers non nuls. Si l’entiercdivise le produit abet s’il est premier aveca, alorscdiviseb.
10/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique
Plus petit commun multiple
Soienta,bdeux entiers non nuls. On noteMa(resp.Mb) l’ensemble des multiples dea(resp. b). L’ensemble Ma,b:=Ma∩ Mbdes multiples communs àaetbest non vide (il contientab), il admet donc un plus petit élément.
Définition On appelleplus petit commun multiple(ppcm) dea,bet on note ppcm(a,b)(ou encorea^b), le plus petit élément deMa,b. Plus généralement, leppcmdes nombresa1, . . . ,an, noté eM ∩ ∙ ∙ ∙ ∩ M. ppcm(a1, . . . ,an), est le plus petit élément da1an
MAT231, Chapitre 1 Chapitre 2, Arithmétique
11/22
Théorème Soienta,bdeux entiers non nuls. On notem:=ppcm(a,b)leur ppcm. L’ensemble des multiples communs àaetbest égal à l’ensemble des multiples dem, c’est-à-direMa,b=Mm.
Corollaire Soienta,bdeux entiers non nuls. On noted:=pgcd(a,b)et 0 0 0 0 m:=ppcm(a,b). On définita,bpara=daetb=db. Alors 0 0 m=da bet, en conséquence,ab=pgcd(a,b)×ppcm(a,b).
[ICorollaire, voir TD.]
12/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique
Nombres premiers
Définition Un nombre entier supérieur ou égal à 2 est ditpremiers’il n’admet pas d’autre diviseur que lui-mme et 1.
Proposition Tout nombre entier supérieur ou égal à 2 possède au moins un diviseur premier.
Proposition Il existe une infinité de nombres premiers.
MAT231, Chapitre 1 Chapitre 2, Arithmétique
13/22
Lemme d’Euclide Soitpun nombre premier. ( 1,sip6∈ Da, 1.SoitaN,a1. Alorspgcd(a,p) = p,sip∈ Da. 2.Soienta,bN. Sipdiviseab, alorspdiviseaoupdiviseb. 3.Soienta1, . . . ,anN. Sipdivise le produita1×. . .×an, alorspdivise au moins un desai.
14/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique
Théorème (Décomposition en facteurs premiers) Soitaun nombre entier supérieur ou égal à 2. Le nombreapeut s’écrire d’une manière et d’une seule (à l’ordre près des facteurs) sous la forme d’un produit,
α α 1k a=p. . .p 1k
de puissances (αjN, αj1) de nombres premiers deux à deux distinctsp1, . . . ,pk.
MAT231, Chapitre 1 Chapitre 2, Arithmétique Idéaux deZet Théorème de Bézout
Idéaux deZet Théorème de Bézout
15/22
Définition SoitAun anneau commutatif. Une partie non videIdeAest un idéalsi, 1.(I,+)est un sous-groupe de(A,+), 2.Iest stable par la multiplication deA, c’est-à-dire, pour tout x∈ Iet pour toutaA,ax∈ I.
16/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique Idéaux deZet Théorème de Bézout
Exemples {0}etAsont des idéaux deA. I I Dans l’anneauZ,aZ:={ak|kZ}(ensemble des multiples dea) est un idéal. I On noteaZ+bZl’ensemble
aZ+bZ:={nZ| ∃(u,v)Zt.q.n=au+bv}.
C’est un idéal deZ.
Théorème (Caractérisation des idéaux deZ) SoitIun idéal deZ. Alors il existe un unique élémentaNtel queI=aZ. SiI 6={0}, l’élémentaest le plus petit élément strictement positif deI.
MAT231, Chapitre 1 Chapitre 2, Arithmétique Idéaux deZet Théorème de Bézout
17/22
Théorème de Bézout Soienta,bZ. Les nombresaetbsont premiers entre eux, si et seulement s’il existe un couple(u,v)d’entiers tel queau+bv=1 (ce couple n’est pas unique).
Théorème de Bézout généralisé Soienta,bZ. Notonsd:=pgcd(a,b)lepgcddes nombresaet b. Alors,aZ+bZ=dZ. En particulier, le pgcd deaetbs’écrit d=au+bvpour un couple(u,v)d’entiers (ce couple n’est pas unique).
18/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique Congruences
Congruences
Définition SoientnZeta,bZ. On dit queaestcongruàb modulo nsi ndiviseab.
Proposition La congruence modulonZest une relation d’équivalence dans Z, compatible avec les opérations deZ.
MAT231, Chapitre 1 Chapitre 2, Arithmétique Congruences
19/22
Proposition Soienta,bZetnZ. Alorsab(modn)si et seulement si aetbont le mme reste dans la division euclidienne parn.
Corollaire Pour toutaZ, il existe un uniquer∈ {0,1, . . . ,n1}tel que ar(modn)(c’est le reste de la division euclidienne deaparn).
[ICompléments sur les congruences, voir DM.]
20/22
MAT231, Chapitre 1 Chapitre 2, Arithmétique Congruences
Proposition (Critères de divisibilité) I Le nombrex=xnxn1. . .x0en baseaest divisible parasi et seulement six0=0. Il est divisible par un diviseurddeasi et seulement six0est divisible pard. I Le nombrex=xnxn1. . .x0en baseaest divisible par(a1) si et seulement sixn+. . .+x0est divisible par(a1). I Le nombrex=xnxn1. . .x0en baseaest divisible par(a+1) n n1 si et seulement si(1)xn+ (1)xn1+. . .+x0est divisible par(a+1).
[ICritères de divisibilité par 2,5,9 et 11 en base 10, voir TD.]
MAT231, Chapitre 1 Chapitre 2, Arithmétique Congruences
21/22
Version Septembre 2008 mat231-chap2-arithmetique-080902.tex (2 septembre 2008)
22/22
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.