Les nombres premiers - Claude Bernard University Lyon 1

1 DOCUMENT 4 Les nombres premiersLa relation de divisibilit e poss`ede un r ole central en arithm etique. C est en particulier unerelation d ordre surNavec 1 pour plus petit el ement. Il est donc naturel de s int eresser dansl ensemble des entiers positifs, diff erents de 1, aux el ements minimaux pour cette relation d ordre,c est-`a-dire aux entiers ne poss edant dansNque deux diviseurs, 1 et eux-m D efinition d un nombre premier et caract erisationsD entierpest premier sip 2et si ses seuls diviseurs dansNsont 1 etlui-m entierpest premier si et seulement sip 2 et si ses seuls diviseurs dansZsont 1, -1,pet deux propositions suivantes vont montrer qu il existe beaucoup de nombres entiern 2admet un diviseur premier. Sinn est pas premieralors il poss`ede un diviseur premierptel quep E( n)( E(.) d esigne la partie enti`ere). premier alorsnconvient. Sinon l ensemble des diviseurs de n compris entre 2etn 1 n est pas vide et poss`ede donc un plus petit el ementp.

2 Comme tout diviseur depestun diviseur den,pest premier. Sin=pm,m N, alorsp md o`up2 pm=net, commepest un entier,p E( n). ensemble des nombres premiers est , .., pnune suite finie dennombres premiers etN= D apr`es laproposition pr ec edenteN+ 1 poss`ede un diviseur premierpqui ne peut etre l un despicar lereste de la division euclidienne deN+ 1 parpiest 1. Donc pour tout entier n, il existe plus dennombres premiers . Leur ensemble est proposition pr ec edente peut etre consid er ee comme un cas particulier duth eor`eme de Dirichlet: siaetbsont deux entiers premiers entre eux alors il existe uneinfinit e de nombres premiers de la formea+bn,n d emonstration de ce th eor`eme estdifficile et utilise les fonctions de variable complexe mais il y a des cas particuliers faciles `a etablir. Par exemple, avec une preuve voisine de celle de la proposition pr ec edente, on montrequ il existe une infinit e de nombres premiers de la forme 4n+ un entierp 2.

3 Les affirmations suivantes sont equivalentes :(1)L entierpest premier.(2)Pour tout entiern Z,p|noupetnsont premiers entre eux.(3)Sip|ab,(a, b) Z2, alorsp|aoup|b( Z/pZest int`egre).(4)L anneauZ/pZest un LES nombres premiers (5) (p 1)! + 1 0 (mod p)(Th eor`eme de Wilson). ) 2). Pour tout entiern, le pgcd depetndivise p doncpgcd(p, n) = 1 oupgcd(p, n) =p. Dans le premier cas,petnsont premiers entre eux et, dans le second, ) 3). Sip|abet sip6|aalorspest premier avecaet le th eor`eme de Gauss entraine quep| ) 4) Soita6=0 etfl application deZ/pZdans lui-m eme d efinie parf(x) =ax. Cetteapplication est injective car sia(x y) =0 alorsp|a(x y) et, commea6=0,p6|ad o`up|x yetx=y. L ensembleZ/pZ etant fini,fest surjective et il existe un entierbtel queab= el ement non nul deZ/pZest inversible etZ/pZest un ) 5). Remarquons d abord que dans (Z/pZ) les quatre affirmations suivantes sont equivalentes:x=x 1,x2 1 = 0, (x 1)(x+1) = 0,x=1 oux= 1 =p 1.

4 SoitRla relation binaired efinie sur (Z/pZ) parxRy x=youx =y est clair queRest une relation d equivalence et il r esulte de la remarque pr ec edente que toutesles classes d equivalence, autres que1 etp 1, poss`edent deux el ements distincts. SoitEunensemble obtenu en prenant un el ement et un seul dans chacune des classes ayant deux el alors (Z/pZ) a un ou deux el ements et on v erifie facilement le th eor`eme de Wilsonpourp= 2 oup= 3. SiE6= alorsp 5 et on 2 = x Exx 1=1d o`u(p 1)! =p 1 = 1 ou encore (p 1)! + 1 0 (mod p).5) 1). Soitdun diviseur positif dep, distinct dep. On a 1 d p 1 d o`ud|(p 1)!.Si(p 1)! + 1 0 (mod p) alorsd|1 doncd= 1 etpest ) Supposons que (Z/pZ) soit un corps et soita [1, p 1] un entier. Il existeb Ztel queab=1 d o`u l existence de Ztel queab 1 = p. Siadivisepalorsadivise 1 et donca= entierpest premier et on a montr e directement que 4) 1).

5 La preuve de la propositionpr ec edente o`u ne figure plus le th eor`eme de Wilson est donc tr`es ) Un idealId un anneauAest ditpremiersiI6=Aetab Iimpliquenta Ioub I. Enutilisant la partie 3) de la proposition pr ec edente on voit que les id eaux premiers deZsont{0}(carZest int`egre) et les id ) Un idealId un anneauAest ditmaximalsi c est un el ement maximal de l ensemble, ordonn epar inclusion, des id eaux deAdistincts deA. En utilisant la propri et ea|b bZ aZ, onvoit que les id eaux maximaux deZsont lespZ,ppremier. Dans la proposition pr ec edentel equivalence des affirmations 1) et 4) n est qu un cas particulier du r esultat : un id ealId unanneau commutatif et unitaireAest maximal si et seulement siA/Iest un D ecomposition en facteurs premiers et Le th eor`eme d existence et d unicit a d ej`a remarqu e que les nombres pre-miers sont pour la relation de divisibilit e les el ements minimaux et une pratique courante etf econde en math ematiques consiste `a d ecomposer les objets `a l aide d objets minimaux.

6 C estce que nous allons faire ici avec les entiers d efinition suivante va permettre de consid erer une d ecomposition en facteurs premierscomme un objet math D ECOMPOSITION EN FACTEURS premiers ET APPLICATIONS33D d ecomposition den Nen facteurs premiers est un couple form e par:(1)une suite finie strictement croissante de nombres premiersp1, .., pk;(2)une suite dekentiers naturels non nuls 1, .., ktels quen=p preuve du th eor`eme affirmant l existence et l unicit e d une d ecomposition en facteurspremiers pour tout entier 2 utilise les propri et es des nombres premiers entre eux (voir ledocument 3) et le lemme :(1)Si un nombre premier divise un produit de facteurs alors il divise l un d eux.(2)Si un nombre premier divise un produit de facteurs premiers alors il est egal `a l und ) Si le nombre premierpne divise aucun desai,i= 1, .., n, alorspest premier avectous lesaiet doncpest premier avec leur ) Evident en utilisant 1).

7 Avant d enoncer le th eor`eme, donnons une notation utile. Soit p un nombre premier etn N . L ensemble des entiersktels quepk|nest fini. Il poss`ede donc un plus grand el ementque l on d esigne parvp(n).Th eor` entiern 2poss`ede une unique d ecomposition en facteurs L < .. < pkla suite strictement croissante des diviseurs premiersdenetm=pvp1(n) (n)k. Sii6=jalorspietpjsont premiers entre eux et il en est de m emepourpvpi(n)ietpvpj(n)j. Il en r esulte quem|n(Corollaire du document 3). Posonsn= >1 alorsqposs`ede un diviseur premierpet commep|nil est egal `a l un despi:p=ph,1 h k. L egalit en=qmentraine quepvph(n)+1h|nen contradiction avec la d efinition devph(n). Doncq= 1 etm=n, ce qui montre que le couple form e par les suitesp1, .., pketvp1(n), .., vpk(n) est une d ecomposition denen facteurs unicit quen=q rro`uq1, .., qrest une suite strictement croissante denombres premiers et i N.

8 Commeqiest un diviseur premier den, on a{q1, .., qr} {p1, .., pk}. Soiti [1, k]. Le nombre premierpidiviseq rrdonc il existeh [1, r] telquepi|q hhd o`upi|qhet finalementpi=qh. Il en r esulte que{q1, .., qr}={p1, .., pk}d o`ur=ketpi=qipour touti [1, k] car les suites (pi) et (qi) sont strictement croissantes. Pard efinition devpi(n), i vpi(n). et s il existehtel que h< vph(n) alorsn=p kk< pvp1(n) (n) (n)k=nce qui est absurde. On a donc i=vpi(n) et l unicit e de la d ecomposition est d emontr preuve pr ec edente est un peu longue mais elle donne aussi la forme pr ecise de lad ecomposition et une fa con de l obtenir. Il en existe des beaucoup plus courtes mais n ayant pasces qualit es. Par exemple, pour l existence de la d ecomposition, on peut faire la d emonstrationsuivante :Si tout entier ne se d ecompose pasen facteurs premiers alors soitn0le plus petit entier n ayantpas de d ecomposition.

9 Commen0n est pas premier,n0 4 etn0poss ede un divieuraavec344. LES nombres PREMIERS2 a n0 1. On an0=abavec 2 b n0 1. Les entiersaetbsont des produits denombres premiers et doncn0aussi d o`u une Exemples d intervention. 1. Applications aux diviseurs d un entier. Pro-pri et es des applicationsvp. Applications aux pgcd et que pour tout nombre premierp,vp(n) est le plus grand entierktel quepk| entiers strictement positifs.(1)Pour tout nombre premierp,vp(ab) =vp(a) +vp(b).(2)L entieradivisebsi et seulement si, pour tout nombre premierp,vp(a) vp(b).(3)Sid=pgcd(a, b),m=ppcm(a, b)alorsvp(d) =min(vp(a), vp(b)),vp(m) =max(vp(a), vp(b)). ) Pour tout nombre premierp, on aa=pvp(a)a ,b=pvp(b)b avecp6 |a etp6 |b . Lelemme entrainep6|a b et, commeab=pvp(a)+vp(b)a b on avp(ab) =vp(a) +vp(b).2) Sia|balors, pour tout nombre premierp,pvp(a)|bet doncvp(a) vp(b). R eciproquement,supposons quevp(a) vp(b) et soitPune ensemble fini de nombres premiers contenant lesdiviseurs premiers deaet deb.

10 On a :b= p Ppvp(b)= p Ppvp(b) vp(a). p Ppvp(a)=a. p Ppvp(b) vp(a)et donca| ) Evident en utilisant 2) et les d efinitions du pgcd et du tout(a, b) N 2,pgcd(a, b)ppcm(a, b) = +m=max(n, m) +min(n, m), la partie 3) de la proposition pr ec edenteentraine, pour tout nombre premierp,vp(pgcd(a, b)) +vp(ppcm(a, b)) =vp(a) +vp(b) d o`upgcd(a, b)ppcm(a, b) =ab(Le corollaire est encore vrai sia= 0 oub= 0.)Le nombre des diviseurs d un kkun entier naturel 2 d ecompos e en facteurs premiers . La partie 2) de laproposition entraine qued|nsi et seulement sid=p kkavec 0 i i, 0 i application qui au diviseurddenfait correspondre ( 1, .., k) est une bijection de l ensembledes diviseurs densur [0, 1] .. [0, k]. Le nombre des diviseurs denest donc ( 1+1)..( k+1)Par exemple, le nombre de diviseurs de 360 = est = 24, le nombre de diviseurs depn, p etant premier, estn+ 1La somme des puissances r-i`emes des diviseurs d un erons toujoursn=p kk.