7/22/2019 TS Sp Chap 2 : Cours sur les Nombres Premiers

1/2

2. Nombres premiers

2.1 Gnralits

Dfinition. Un entier naturel est premier lorsquil ne possde que deux diviseurs positifs,

savoir 1 et lui-mme.

Remarque. Ainsi 0 et 1 ne sont pas premiers.

Le plus petit nombre premier est 2.

Un entier qui nest pas premier estcompos.

Les diviseurs de ncompris entre 2 et n1 sont ses diviseurs propres; 1 et n sont sesdiviseurs triviaux.

Thorme. Tout entier natureln 2 admet comme plus petit diviseur propre un entier premier

p. Si n est compos, on a de plus 2 p

n.

Preuve. Si n est premier alors p = n est trivial. Si n est compos, lensemble E des

diviseurs 2 de n est une partie non vide de N. Il possde donc un plus petit lment

p. Si ptait compos, il serait divisible par un entier qvrifiant 2 q < p. Cet entier q

diviserait alorsn, contrevenant ainsi la dfinition de p. Finalement pest premier.

Si n= pqavec 2 p qalors p2 pq= n do p

n.

Thorme (Euclide). Lensemble des nombres premiers est infini.

Preuve. Supposons que cet ensemble soit fini : P ={p1, , pn}. Lentier a= p1p2 pn+ 1 nepossde aucun diviseur premier. Le thorme prcdent montre que cest impossible.

2.2 Dcomposition

Thorme. Tout entier 2 se dcompose en produit de facteurs premiers, cette dcomposition

tant unique lordre prs.

Preuve. Existence.Soit Pn = tout entier compris entre 2 et n possde une dcompo-

sition en facteurs premiers . Pour n = 2 cest trivial. Si Pn est vraie : soit n+ 1 est

premier, soit il est compos et donc est le produit de de entiers nqui se dcomposent,

par hypothse, en produit de facteurs premiers. Ainsi n+ 1 se dcompose aussi et Pn+1est donc vraie. Par rcurrence, Pn est vraie pour tout n 2.

Unicit. Voir les lments qui y conduisent dans les exercices.

Remarque. Cette dmonstration dexistence nest pas constructive. Lalgorithme (exercice !)

de dcomposition cherche diviser un entier nautant que possible par 2, par 3, par 5, etc.

129

7/22/2019 TS Sp Chap 2 : Cours sur les Nombres Premiers

2/2

Thorme. Sia= p11 pkk etb= p11 pkk , oi, i 0 alors pgcd(a, b) =pmin(1,1)1 pmin(k,k)ket ppcm(a, b) =p

max(1,1)1 pmax(k,k)k .

Preuve. Exercice.

Corollaire. Si d= pgcd(a, b) et m= ppcm(a, b) alors dm= ab.

Preuve. Il suffit essentiellement de noter que min(x, y) + max(x, y) =x+y.

2.3 Petit thorme de Fermat

Thorme. Si a est un entier et p un nombre premier alors ap a mod p. Si de plus p nedivise pas aalors ap1 1 modp.

Preuve. Voir exercice 2.16.

Remarque. Le petit thorme de Fermat a t nonc par Fermat en 1640, prouv par

Leibniz avant 1683 et publi (et gnralis) par Euler en 1736.

Il ne faut pas confondre ce rsultat avec le grand thorme de Fermat, plus facile

noncer (il nexiste pas de solutions entires non triviales de xn +yn = zn pour n 3)

mais bien plus difficile dmontrer (preuve trs longue et difficile dune conjecture plus

gnrale par Wiles en 1994).

Le petit thorme de Fermat est bien plus fondamental que le grand ...

LarciproquedupetitthormedeFermatestfausse,etmmetrsfausse.

130