Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Cours sur les nombres premiers

3 pages
Nombres premiers Dans cette partie, on appelle nombre tout entier naturel non nul. 1 DØ?nition DØ?nition 1 Soit p un nombre. On dit que p est un nombre premier si p 2 et si les seuls diviseurs de p sont 1; 1; p et p. On noteP l?ensemble des nombres premiers. Exemple 2 Les entiers 2;3;5;7 et 11 sont des nombres premiers. Les entiers 1 et 4 ne le sont pas. Remarque 3 Si p est un nombre premier alors pour la plupart des nombres q : p est premier avec q, mais attention 4 est premier avec 15 mais 4 n?est pas un nombre premier (15 non plus). 2 Crible d?EratosthŁne Recherchons tous les nombres premiers plus petits que 100 par exemple. Le nombre 1 n?est pas un nombre premier. On l?enlŁve. Le nombre 2 est premier. Tous les multiples de 2 autres que 2 ne sont pas premiers et sont donc otØs. Le nombre 3 est premier. On enlŁve ensuite tous les multiples de 3 strictement supØrieurs ? 3 (ils ne sont pas premiers). Le plus petit nombre restant est 5, qui est donc premier. On enlŁve tous les multiples de 5 strictement supØrieurs ? 5. Cette mØthode permet donc de proche en proche d?obtenir les nombres premiers plus petits que 100. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 3 Nombres premiers et divisibilitØ Proposition 4 Soit p un nombre, p 2.
Voir plus Voir moins

1

Nombres

premiers

Dans cette partie, on appelle nombre tout entier naturel non nul.

Dénition

Dénition 1Soitpun nombre. dit que Onpest un nombre premier sip2et si les seuls diviseurs
depsont1;1; petp.
On notePlensemble des nombres premiers.

Exemple 2Les entiers2;3;5;7et11sont des nombres premiers. Les entiers1et4ne le sont pas.

Remarque 3Sipest un nombre premier alors pour la plupart des nombresq:pest premier avec
q, mais attention4est premier avec15mais4nest pas un nombre premier (15non plus).

2

Crible dEratosthène

Recherchons tous les nombres premiers plus petits que100par exemple.
Le nombre 1 nest pas un nombre premier. On lenlève.
Le nombre2 Tous les multiples deest premier.2autres que2ne sont pas premiers et sont donc
otés.
Le nombre3est premier. enlève ensuite tous les multiples de On3strictement supérieurs à3(ils
ne sont pas premiers).
Le plus petit nombre restant est5, qui est donc premier. On enlève tous les multiples de5
strictement supérieurs à5.

Cette méthode permet donc de proche en proche dobtenir les nombres premiers plus petits que
100.

3

12 345678
2 1 2 223 2 5 2 6 2 7 2 82 4
414 243 5 44 4 6 4474 8
61 6 36 2 6 5 6 4 6 6676 8
8 1 8 283 5 88 4 8 8 8 7 8 6

9 1 0
293 0

111 213 1 5 1 61 417
31 3 4 3 5 33 2 3 3 637

4 9 5 0 5 1 5 253 5 55 4 7 5 6 5
6 9 7 0717 2737 4 7 5 7 6 7 7
89 2 9 3 9 4 9 5 99 0 1 9 6 997

Nombres premiers et divisibilité

Proposition 4Soitpun nombre,p2. Il y a équivalence entre :

1. lentierpest un nombre premier.

2. les seuls entiers non premiers avecpsont les multiples dep.

3. le nombrepest premier avec1;2; : : : ; p1.

1 8

3 8

5 8
7 8

9 8

19

3 9

59
79

9 9

2 0

4 0

6 0

8 0

1 0 0

Démonstration.On va montrer1 =)2 =)3 =)1
Supposons quepest un nombre premier. Soitaun entier non premier avecp. Soitd=pgcd(a; p),
on ad6= 1, orddivisepetdest positif doncd=p. Commeddivise aussia, on en déduit quep
divisea.
Soitpque les seuls entiers non premiers avecun nombre tel psont les multiples dep. Soit
k2 f1;2; : : : ; p1getd=pgcd(k; p). Commeddivisep, on ad= 1oud=p. Sidétait égal àp
alorspteraisividket on auraitpk Doncce qui est exclu.d= 1doncpetksont premiers entre
eux.
Supposons que le nombrepest premier avec1;2; : : : ; p1. Soitdun diviseur positif dep. Alors
dpet pgcd(d; p) =d. Si1< d < palors pgcd(d; p) = 1par hypothèse et lon auraitd= 1. Donc
d= 1oud=p. Doncpest un nombre premier.

Corollaire 5Soitpun nombre premier. Pour touta2Z, les entiersaetpsont premiers entre eux
si et seulement sipne divise pasa.

Corollaire 6Soitpetp0deux nombres premiers. Alorspetp0sont premiers entre eux si et seule-
ment sip6=p0.

Démonstration.Si pgcd(p; p0) = 1alorsp6=p0.
Sip6=p0alorsp0ne divise pasp(sinonpne serait pas un nombre premier) et par conséquent
pgcd(p; p0) = 1.

Lemme 7Lemme dEuclide. Soitaetbdeux entiers relatifs et soitpun nombre premier. Sip
diviseabalorspdiviseaoupdiviseb.

Démonstration.Il existeq2Ztel queab=p. Sipne divise pasaalors alorspest premier
aveca. Doncpdiviseb(théorème de Gauss).

4

Décomposition en facteurs premiers

Dénition 8Soita2N. Un nombre premierpqui diviseasappelle un facteur premier dea.

Exemple 9Lentier3est un facteur premier de12.
Les entiers1et1nadmettent pas de facteur premier.

Exemple 10Soita= 491. On veut savoir siaest premier ou pas. On teste siaest divisible par
2, par 3, par 5, par 7, par 11, par 13, par 17, par 19. Le nombre premier suivant est 23. Comme
232= 529>491,491est un nombre premier.

Proposition 11LensemblePdes nombres premiers est inni.

Démonstration.On sait quePest non vide (il contient les entiers2,3,5, etc). Supposons quil
est ni, de cardinalN, cest à dire queP=fp1; : : : ; pNg. Posons alorsa += 1p1  pN. Comme
a2, il admet un facteur premierpdoncp2 Pdonc il existemtel quep=pm. Mais alorspm
diviseap1  pN= 1, ce qui est impossible.

Dénition 12Soita2Z. Soitpun nombre premier. Lensemblefm2N;tels quepmjagadmet
un plus grand élément, notévp(a)et appelépvaluation deaou indice de multiplicité depdansa
ou exposant depdansa.

Exemple 1312 = 223doncv2(12) = 2etv3(12) = 1.
Six= 35alorsv3(x) =etv5(x) =.

Théorème 14Décomposition en facteurs premiers.Soita2Ztel quejaj 2. Il existe
"2 f1;1g,s2N, des nombres premiers0 < p << p  < pet des entiers naturels non nuls

1 2s
m1; : : : ; mstels que
a=" p1m1  psms
De plus, cette décomposition est unique etm1=vp1(a); : : : ; ms=vps(a).

Démonstration.Unicité de la décomposition. Avec des notations évidentes, supposons que
a="p1m1  psms="0q1n1  qrnr. Sia >0alors"="0= 1et sia <0alors"="0=1.
Soiti,1is que. Supposonspisoit di¤érent deq1; : : : ; qr. Alorspiest séparément premier
avecq1; : : : ; qrdonc séparément premier avecq1n1; : : : ; qrnrdonc premier avecq1n1  qrnr=p. Mais
ceci est en contradiction avec le fait quepiest un facteur premier dep montre ainsi que. On
fp1; : : : ; psg=fq1; : : : ; qrg en déduit alors que. Ons=rpuis quep1=q1; : : : ; ps=qs.
Existence de la décomposition. Soita2. On pose"= 1. Considérons lensemblePdes facteurs
premiers deani (tout facteur premier est inférieur à sait quil est non vide, et quil est . Ona).
Soitp1; : : : ; psses éléments, avecp1< p2  < ps chacun de ces facteurs, soit. PourMi=fm2
N;pimjag. Ce sont des ensembles non vides (par dénition despi) et nis (pimja=)pima=)
mln(a)=ln(pi)). Soitmile plus grand élément deMi. Commeaest séparément divisible par
p1m1; : : : ; psmspremiers entre eux deux à deux,aest divisible par leur produit. Il existeq2Ntel
quea=p1m1  psmsq. Siq2,qadmet un facteur premier qui serait aussi un facteur premier de
a. Il existe alorsiavec1istel queq=pi alors. Maispimi+1divisea, ce qui est impossible par
dénition demi. Doncq= 1.
Sia 2, on pose"=1et on décomposejaj.

Exemple 15Lentiera= 84admet pour décomposition en facteurs premiersa= 2237.

Proposition 16Soitaetb pour tout nombre premier Alorsdeux entiers relatifs non nuls.
vp(ab) =vp(a) +vp(b)
Lentieradivisebsi et seulement si pour tout nombre premierp,vp(a)vp(b)

Proposition 17Soita1; : : : ; andes entiers relatifs non nuls. a : On

pgcd(a1; : : : ; an) =Yppet ppcm(a1; : : : ; an) =Ypp
p2Pp2P

oùp= min(vp(a1); : : : ; vp(an))etp= max(vp(a1); : : : ; vp(an))pour toutp2 P.

Proposition 18
est pair.

Soita2N. Alorsaest un carré parfait si

p,

et seulement si pour toutp2 P,vp(a)

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin