Dans ce qui suit, entier est synonyme d'entier relatif 1 Divisibilité dans Z a) Diviseurs et multiples Définition Soit a et b deux entiers
Previous PDF | Next PDF |
[PDF] Algèbre 1 Généralités et Arithmétique dans Z Table des - Unblogfr
Généralités et Arithmétique dans Z Table des matières Z, l'ensemble des entiers relatifs, Z = { , −2, −1, 0, 1, 2, } (voir cours d'Analyse) Ce n'est pas le
[PDF] Arithmétique dans Z - Maths-francefr
1 Divisibilité dans Z 1 1 Définitions Définition 1 1) Soient a et b deux entiers relatifs tels que a = 0 On dit que a divise b ou que a est un diviseur de b si et
[PDF] Cours darithmétique
mais il est fortement recommandé de lire ce chapitre avant d'aborder le cours Les chapitres ou 2 2 Généralités sur les groupes finis 6 Arithmétique Il existe des variantes de démonstrations par récurrence, par exemple : Variante 1 Pour
[PDF] Résumé du cours darithmétique
Dans ce qui suit, entier est synonyme d'entier relatif 1 Divisibilité dans Z a) Diviseurs et multiples Définition Soit a et b deux entiers
[PDF] Cours darithmétique
Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él` eves pré- Z ensemble des entiers relatifs Q ensemble des nombres rationnels R Une récurrence directe permettra ensuite de l'avoir dans toute sa généralité
[PDF] Chapitre 4 :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 Etant
[PDF] Algèbre et arithmétique pour Master-1
Ce livre est écrit à partir d'un cours dans le cadre de la première année du Master Il existe une analogie profonde entre l'ensemble Z des nombres entiers et l'ensemble Nous donnons ici les premières généralités sur ces anneaux qui
[PDF] ALGÈBRE ET ARITHMÉTIQUE 1 - Université de Rennes 1
définitions qui seront données au fil de ce cours) et des propriétés qui découlent de ces concepts, énoncées 6 CHAPITRE 1 LOGIQUE ET THÉORIE DES ENSEMBLES de l'addition, qui sera démontrée ci-dessous en toute généralité
[PDF] Cours arithmétique et groupes Licence première année, premier
Cours arithmétique et groupes z = x ou z = y ; on le notera x−1 (on montrera en exercice qu'un prédécesseur On peut supposer sans perte de généralité
[PDF] Arithmétique - Maths au lycée
Soit a et b deux entiers relatifs tels que : b 0 Il existe un entier relatif n tel que : nb a On dit que Z est archimédien Démonstration 1er cas
[PDF] generally
[PDF] generate code for aiims 2019
[PDF] generation of alternating current
[PDF] generation of code for final registration aiims
[PDF] generation of computer 1st to 5th
[PDF] generation of computer notes
[PDF] generation of computer notes pdf
[PDF] generation of computer ppt
[PDF] generation of computer wikipedia
[PDF] generation of programming languages
[PDF] generations of programming languages pdf
[PDF] generic abn form pdf
[PDF] generic type java
[PDF] generics collection
Maths discr`etes, 2012-2013Universit´e Paris-Sud
R´esum´e du cours d"arithm´etique
Les ensemblesNetZ
N=0,1,2,3,...est l"ensemble des entiers naturels (entiers positifs). Z=...,?2,?1,0,1,2,3,...est l"ensemble des entiers relatifs. N =N 0(entiers strictement positifs) etZ=Z 0(entiers relatifs non nuls). Dans ce qui suit, entier est synonyme d"entier relatif.1 Divisibilit´e dansZ
a) Diviseurs et multiples D´efinition.Soitaetbdeux entiers. On dit queadivisebs"il existe un entierktel queb=ka. On noteab. On dit ´egalement queaest undiviseurdebou quebest unmultipledea. Remarque.Siadiviseb, alorsadivise?b,?adivisebet?adivise?b. b) Propri´et´es Propri´et´es 1.Soita,b,cdes entiers relatifs. (1) Sib= 0 etadivisebalorsa b. En particulier,bZa un nombre fini de diviseurs. (2) Siadivisebetbdiviseaalorsa=boua=?b. (3) Siadivisebetbdivisecalorsadivisec. (4) Siadivisebetc, alors, pour tous entiersnetm,adivisenb+mc. La propri´et´e (4) se g´en´eralise sans difficult´e `a 3 termes ou plus.2 Division euclidienne
Th´eor`eme 2 (th´eor`eme de la division euclidienne).SoitaZetbN. Il existe des entiersqetrtels quea=bq+ret 0r < b. De plus,qetrsont uniques. D´efinition.SoitaZetbN. Effectuer ladivision euclidiennedeaparb, c"est trouver les entiersqetrtels quea=bq+ravec 0r < b.qest lequotientetrest lerestede la division euclidienne deaparb. Propri´et´e 3.Le reste de la division euclidienne deaparbest nul si et seulement sibdivisea.3 PGCD
a) D´efinition D´efinition.Soita,bZ. Le plus grand entier qui divise `a la foisaetbs"appelle leplus grand commun diviseuroupgcddeaetb. On le notepgcd(a,b).Remarque.pgcd(a,b) = pgcd(a,b).
Propri´et´e 4.Soita,bZ. Siadivisebalors pgcd(a,b) =a. 1 b) Algorithme d"Euclide Th´eor`eme 5 (lemme d"Euclide).Soita,bZ. S"il existe des entiersketsavecs= 0 tels quea=bk+salors les diviseurs communs `aaetbsont exactement les diviseurs communs `a bets, et pgcd(a,b) = pgcd(b,s).Algorithme d"Euclide.
SoitaZetbN. On cherched= pgcd(a,b). On noter0=b. On effectue des divisions euclidiennes successives tant que le reste est non nul. a=r0q1+r10< r1< r0 b=r1q2+r20< r2< r1 r1=r2q3+r30< r3< r2.
r n3=rn2qn1+rn10< rn1< rn2 r n2=rn1qn+rn0< rn< rn1 r n1=rnqn+1+ 0rn+1= 0 Th´eor`eme 6.Le pgcd deaetbest le dernier reste non nul obtenu par l"algorithme d"Euclide. Remarque.Sir1= 0, c"est quebdivisea, donc pgcd(a,b) =b=r0. Propri´et´e 7.Soita,bZ. Siddiviseaetbalorsddivise pgcd(a,b).Remarque.On peut d´efinir le pgcd de 3 entiers ou plus. La propri´et´e 7 restevalable. Il n"y a
pas d"´equivalent de l"agorithme d"Euclide pour calculer le pgcd de 3 entiers. On peut utiliser la propri´et´e suivante : sid= pgcd(a,b) alors pgcd(a,b,c) = pgcd(d,c). c) Nombres premiers entre eux D´efinition.Soitaetbdeux entiers non nuls. On dit queaetbsontpremiers entre euxsi pgcd(a,b) = 1. On dit aussi queaest premier avecb. Propri´et´e 8.Soita,bZetd= pgcd(a,b). Alorsa detb dsont premiers entre eux.4 Th´eor`emes de B´ezout et de Gauss
a) Th´eor`eme de B´ezout Th´eor`eme 9 (th´eor`eme de B´ezout).Soitaetbdeux entiers non nuls.1) Il existe des entiers relatifsuetvtels queau+bv= pgcd(a,b).
2) S"il existe des entiersuetvtels queau+bv= 1 alorsaetbsont premiers entre eux
b) Comment trouver une relation de B´ezout Trouver une relation de B´ezout pouraetb, c"est trouveruetvtels queau+bv= pgcd(a,b). On applique l"algorithme d"Euclide `aaetb. Gardons les notations de 3b). On a pgcd(a,b) =rn. On part de l"´egalit´e donnant le pgcd et on ´ecrit : pgcd(a,b) =rn2?rn1qn.() Puis on utilise la ligne pr´ec´edente dans l"algorithme d"Euclide pour exprimerrn1(reste avec l"indice le plus ´elev´e dans ()) :rn1=rn3?rn2qn1, on remplacern1dans (), on a : pgcd(a,b) =rn2?(rn3?rn2qn1)qn=?rn3qn+rn2(1 +qnqn1).()On utilise la ligne pr´ec´edente dans l"algorithme d"Euclide pour exprimerrn2(reste avec l"indice
le plus ´elev´e dans ()), puis on remplacern2dans (). On continue ainsi jusqu"`a ´eliminer les restesrn1,rn2,...,r2,r1. On a alors le pgcd en fonction deaetb. 2c) Th´eor`eme de GaussTh´eor`eme 10 (th´eor`eme de Gauss).Soita,b,cdes entiers non nuls. Siadivisebcet sia
est premier avecb, alorsadivisec. Th´eor`eme 11 (corollaire du th´eor`eme de Gauss).Soita1,a2,bdes entiers tels quea1et a2sont premiers entre eux. Sia1eta2divisentb, alors le produita1a2diviseb.
Remarque.Le th´eor`eme 11 se g´en´eralise `a 3 entiers ou plus : sia1,a2,...,ansont deux `a deux
premiers entre eux et divisentb, alorsa1a2andiviseb. d) R´esoudre l"´equationax+by=c On veut trouver toutes les solutions enti`eres de l"´equation :ax+by=c(E) o`ua,b,csont des entiers donn´es aveca,bnon nuls, etx,ysont les inconnues. Th´eor`eme 12.L"´equation (E) admet des solutions si et seulement si pgcd(a,b) divisec.M´ethode pour r´esoudre l"´equation (E).
Si pgcd(a,b) ne divise pasc, il n"y a pas de solution (th´eor`eme 12). Si pgcd(a,b) divisec, il y a des solutions par le th´eor`eme 12. Voici comment les trouver.0) Simplifier l"´equation
Si pgcd(a,b) divisec, on divise l"´equation par pgcd(a,b), on trouve que (E) est ´equivalente `a
a x+by=c o`ua=a/pgcd(a,b),b=b/pgcd(a,b) etc=c/pgcd(a,b) (a,b,csont des entiers).1) Solution particuli`ere
Les entiersaetbsont premiers entre eux (propri´et´e 8). Par le th´eor`eme de B´ezout, il existe
des entiersuetvtels queau+bv= 1. Alorsx0=cuety0=cvforment une solution particuli`ere de (E) carax0+by0=c(au+bv) =c.2) Recherche de toutes les solutions
Exprimons les autres solutions en fonction de la solution particuli`ere (x0,y0). a x+by=cax+by=ax0+by0a(x?x0) +b(y?y0) = 0 SoitX=x?x0etY=y?y0. Pour r´esoudre (E), il est ´equivalent de r´esoudre aX=?bY(E)
a etbsont premiers entre eux etbdiviseaX, doncbdiviseXpar le th´eor`eme de Gauss, autrement dit il existekZtel queX=kb. On a alorskab=?bY, et en simplifiant par b = 0 on trouveY=?ka. On vient de montrer que si (X,Y) est solution de (E") alors il existekZtel queX=kb,Y=?ka. On v´erifie facilement l"implication inverse : siX=kb etY=?ka, (X,Y) est bien une solution de (E") pour toutkZ. Les deux implications donnent une ´equivalence : (X,Y) solution de (E") kZ,X=kb,Y=?ka. Par cons´equent, l"ensemble des solutions de (E) est :S={(x0+kb,y0-ka)|k?Z}aveca=a
pgcd(a,b)etb=b pgcd(a,b).Remarque.Ne pas apprendre par coeur ce r´esultat, mais refaire la m´ethode pr´ec´ed´ente.
35 Nombres premiers
a) Reconnaˆıtre un nombre premier D´efinition.Un entiern2 estpremiersi ses seuls diviseurs positifs sont 1 etn. Propri´et´e 13.Si l"entiern2 n"est divisible par aucun nombre premierp n, alorsnest un nombre premier. Th´eor`eme 14 (th´eor`eme d"Euclide).Il existe une infinit´e de nombres premiers. b) D´ecomposition en produit de facteurs premiers Th´eor`eme 15 (d´ecomposition en facteurs premiers).Tout entiern2 peut s"´ecrire de fa¸con unique n=p1p2pr, o`urNetp1,p2,...,prsont des nombres premiers avecp1p2 pr.D´efinition.SoitnNetpun nombre premier.
Sipdivisen, on dit quepest unfacteur premierden
Le plus grand entierktel quepkdivisens"appellel"exposant depdansn.Dans le th´eor`eme 15, on peut regrouper les premiers identiques,on obtient l"´enonc´e suivant :
Th´eor`eme 15" (d´ecomposition en facteurs premiers)Tout entiern2 peut s"´ecrire de fa¸con unique n=pα11pα22pαss o`up1,...,pssont des nombres premiers distincts avecp1< p2<< ps, etα1,...,αsN. Remarque.Dans le th´eor`eme 15", l"exposant depidansnestαi. Si un nombre premierp n"apparaˆıt pas dans la d´ecomposition den, son exposant est 0. c) Application `a la divisibilit´e Th´eor`eme 16 (application de la d´ecomposition en facteurs premiers `a la divisibi- lit´e).Soitaetbdes entiers strictement positifs. Pour tout nombre premierp, notonsα(p) l"exposant depdansaetβ(p) l"exposant depdansb. Alorsadivisebsi et seulement si pour tout nombre premierpon a :α(p)β(p). Th´eor`eme 17 (application de la d´ecomposition en facteurs premiers au pgcd).Soit a,bNetpun nombre premier. Soitα(p) l"exposant depdansaetβ(p) l"exposant dep dansb. Alors l"exposant depdans pgcd(a,b) est min(α(p),β(p)). Remarque.Le th´eor`eme 17 reste valable pour calculer le pgcd de 3 entiers ou plus.6 PPCM
D´efinition.Soitaetbdeux entiers non nuls. Le plus petit entier strictement positif qui est `a la fois multiple deaetbs"appelle leplus petit commun multipleouppcmdeaetb. On le noteppcm(a,b).Remarque.ppcm(a,b) = ppcm(a,b).
Propri´et´e 18.Soita,bZ. Sicest un multiple deaetb, alorscest un multiple de ppcm(a,b). 4 Th´eor`eme 19 (application de la d´ecomposition en facteurs premiers au ppcm).Soit a,bNetpun nombre premier. Soitα(p) l"exposant depdansaetβ(p) l"exposant dep dansb. Alors l"exposant depdans ppcm(a,b) est max(α(p),β(p)). Th´eor`eme 20 (relation entre pgcd et ppcm).Sia,bZ, pgcd(a,b).ppcm(a,b) =ab.Remarque.On peut d´efinir le ppcdm de 3 entiers ou plus. La propri´et´e 18 et leth´eor`eme