n est un nombre premier lorsqu’il a exactement deux diviseurs entiers naturels distincts : 1 et lui-même.
Pour montrer qu’un nombre n n’est pas premier, il suffit de trouver un diviseur de n différent de 1 et de lui-même. On essaiera donc d’écrire n comme un produit de nombres entiers.
Il y a une infinité de nombres premiers.
Soit n∈N, avec n≥4.
Si n n’est pas un nombre premier, alors n admet au moins un diviseur premier p tel que 2≤p≤n.
Si n n’admet aucun diviseur premier inférieur à n, alors n est un nombre premier.
En particulier, les nombres premiers inférieurs à 100 sont :
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Soit n>2, un nombre entier non premier.
n est le produit de nombres premiers : il existe des nombres premiers p1, p2, …, pk distincts et des entiers a1, a2, …, ak appartenant à N∗ tels que :
n=p1a1×p2a2×…×pk−1ak−1×pkak
Cette décomposition de n en produit de facteurs premiers est unique.
Soit n un nombre entier naturel non premier.
L’écriture suivante s’appelle la décomposition de n en produit de facteurs premiers :
n=p1a1×p2a2×…×pk−1ak−1×pkakavec, pour tout i∈{1,…,k} : {pi est un nombre premierai∈N∗
Si n>2, soit il est premier, soit il peut être décomposé en produit de facteurs premiers.
Méthodologie pour décomposer n en produit de facteurs premiers :
On teste la divisibilité de n par les nombres premiers dans l’ordre croissant.
Soit p le plus petit nombre premier qui divise n.
On trouve le quotient q de n par p : n=qp.
On teste de nouveau la divisibilité de q par p :
si q est divisible par p, on procède comme ci-dessus, on trouve son quotient et on teste sa divisibilité par p ;
sinon, on teste la divisibilité de q par le nombre premier immédiatement supérieur à p.
On continue ce procédé jusqu’à obtenir un quotient égal à 1.
Soit n un nombre entier naturel non premier dont la décomposition en facteurs premiers est : n=p1a1×p2a2×…×pk−1ak−1×pkak.
Les diviseurs positifs de n sont les nombres entiers naturels de la forme :
p1b1×p2b2×…×pk−1bk−1×pkbkouˋbi∈N∗ et 0≤bi≤ai pour tout entier naturel i entre 1 et k
Soit a et b deux nombres de N∖{0,1} non premiers entre eux.
PGCD(a;b) est le produit des nombres premiers communs à leur décomposition en facteurs premiers, affectés du plus petit exposant.
Petit théorème de Fermat
Petit théorème de Fermat : Soit n∈N∗ et p est un nombre premier qui ne divise pas n.
p divise np−1−1 :
np−1≡1[p]
Ce théorème permet de résoudre des équations à congruence avec de grands nombres.
Corollaire : Soit p un nombre premier et n∈N.
p divise np−n :
np≡n[p]
L’intérêt de ce corollaire peut être énoncé ainsi : un entier n élevé à la puissance du nombre premier p a le même reste dans la division euclidienne par p que n.