Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Ensemble des nombres premiers

Nous allons dans cette partie introduire le concept de nombre premier et donner quelques résultats historiques.

Notion de nombre premier

Le concept de nombre premier semble être connu depuis plus de 25000 ans, bien avant l’apparition de l’écriture. Commençons par en donner une définition précise, même si le lecteur la connaît sans doute déjà.

Définition

Un entier naturel est dit premier s’il admet exactement deux diviseurs dans : 1 et lui-même.

Example 1.1. Des entiers premiers ou pas

  • Voici quelques nombres premiers : 2,3,5,7,11,13,17,19,23,29,31,...

  • Et quelques nombres non premiers : 0,1,4,6,8,9,10,12,14,15,16,...


[Note]

Bien saisir que 1 n'est pas un nombre premier puisqu'il n'admet qu'un seul diviseur.

Ces nombres ont de tout temps fasciné les mathématiciens et même le grand public. La découverte du nouveau plus grand nombre premier connu a par exemple toujours eu un écho considérable, même dans les médias généralistes. A l'heure où l'auteur écrit ces lignes, il s'agit de 2 74207281 - 1 , qui comporte plus de 22 millions de chiffres dans son écriture décimale.

[Note]

Les nombres de la forme 2 n - 1 sont appelés nombres de Mersenne en hommage au français Marin Mersenne, moine mathématicien du 16e siècle. Une condition nécessaire mais non suffisante pour qu'un nombre de cette forme soit premier est que l'exposant n soit lui-même premier. Ce fait sera démontré lors de la séance d'exercices.

Théorème d'Euclide

Le théorème suivant, dû à Euclide, est l'un des plus célèbres de l'arithmétique. Il stipule que si un nombre premier divise un produit alors il divise nécessairement l'un de ses facteurs.

Théorème d'Euclide

Soient a,b élément de et p un nombre premier.

Si p | a b alors p | a ou p | b .

Démonstration

Si p | a il n'y a rien d'autre à prouver.

Sinon, puisque p est premier, on a nécessairement PGCD ( a , p ) = 1 . D’après le théorème de Gauss, on aura alors p | b .

[Note]

Pour la petite histoire, voici la formulation utilisée par Euclide dans ses "Eléments", Livre VII : "si deux nombres se multipliant l’un l’autre produisent un certain nombre et si un nombre premier mesure leur produit, il mesurera aussi l’un des nombres initiaux".

Ensemble des nombres premiers

Le but de cette sous-partie est de prouver qu'il y a une infinité de nombres premiers. Commençons par ce résultat :

Théorème

Tout entier naturel n supérieur ou égal à 2 admet au moins un diviseur premier.

Démonstration

Si n est premier, comme il se divise lui même, le résultat est prouvé.

Sinon, n admet des diviseurs différents de 1 et n. Soit p le plus petit d’entre eux. Il existe alors un entier q tel que n = p q .

Montrons que p est nécessairement premier. Dans le cas contraire, il admettrait un diviseur m tel que 1 < m < p . Il existerait donc un entier r tel que p = m r . En remplaçant cette expression de p dans celle de n on obtient n = m r q . Ceci est absurde car m serait alors un diviseur de n strictement plus petit que p. On en conclut que p est premier.

Nous sommes maintenant en mesure d'énoncer et de démontrer cette propriété d'infinitude des nombres premiers.

Corollaire

L’ensemble des nombres premiers est infini.

Démonstration

On raisonne par l’absurde en supposant qu’il existe un nombre fini de nombres premiers : p 1 , p 2 ,..., p n .

Posons N = p 1 p 2 . . . p n + 1 . D'après le théorème précédent N admet un diviseur premier. Ainsi il existe i, 1 i n , tel que p i | N . D'autre part il est clair que p i | p 1 p 2 . . . p n . Les deux divisibilités précédentes impliquent alors que p i | 1 . Ce qui est évidemment absurde car p i étant un nombre premier il est strictement supérieur à 1.

[Note]

Il existe de nombreuses preuves de ce résultat, les unes variations directes de celle-ci, les autres beaucoup plus originales et sophistiquées.

[Note]

Ce corollaire signifie en particulier qu'il n'existe pas de nombre premier plus grand que tous les autres.

Test naïf de primalité

D'après la définition, pour tester le fait qu’un nombre n soit premier ou pas, il suffit de prendre tous les entiers de 2 à n - 1 et regarder s’ils divisent n. Si l’on trouve un diviseur parmi eux, cela signifie que n n’est pas premier. Sinon, il l’est.

On peut améliorer un peu cette recherche de diviseurs en se limitant aux entiers entre 2 et n . En effet, si n se décompose en n = p q , nécessairement l'un des deux entiers p ou q sera inférieur ou égal à n . Si ce n'était pas le cas, i.e. si les deux entiers p et q étaient tous deux strictement supérieurs à n , pq serait strictement supérieur à n, ce qui est absurde car p q = n .

Les remarques précédentes conduisent à cet algorithme testant si un entier est premier ou non :

def prime(n):
    if n == 1:
        return False
    m = 2
    while m*m <= n:
        if n % m == 0:
            return False
        m += 1
    return True
[Note]

On utilise bien sûr une boucle while pour arrêter les itérations dès que l'on trouve un diviseur.

L’algorithme précédent se révèle inefficace pour de grands nombres car il est très lent.

Si l’on dispose d’une table de nombres premiers, d'après le théorème d'Euclide il suffit de tester la divisibilité de n par ceux-ci. Le gain de temps est alors appréciable. Par exemple, si l'on connaît tous les nombres premiers inférieurs à 100, on testera la primalité de tous les nombres inférieurs à 100 2 = 10000 .

Il existe cependant d’autres types d’algorithmes, certains même probabilistes, qui sont beaucoup plus rapides. Ils dépassent néanmoins de très loin le niveau de ce cours.

Crible d'Eratosthène

Dans cette sous-partie nous allons présenter une méthode élémentaire et historique pour dresser une table de nombres premiers. Elle est dûe au grec Eratosthène (276 av J.C. - 194 av. J.C.).

Supposons que l'on souhaite obtenir tous les nombres premiers inférieurs à 100.

On commence par écrire dans un tableau tous les nombres de 2 à 100 :

On marque ensuite (ici en rouge) tous les multiples de 2, excepté 2 lui même.

Puis on marque (ici en vert) tous les multiples de 3 non encore marqués, sauf 3.

On procède de même avec 5 (en bleu).

Plus généralement, après un marquage, on prend le premier entier non marqué qui le suit, et on marque ses multiples excepté lui-même. On s’arrête ici à 10, car 10 = 100 .

Les nombres non marqués ne sont multiples d’aucun autre et sont donc premiers.

Voici donc ce que l'on obtient finalement :

Voici pour conclure cette sous-partie une implémentation en Python de ce crible d'Eratosthème :

def eratosthene(n):
    L = [True for i in range(n+1)]
    L[0] = L[1] = False
    for i in range(2,n+1):
        if L[i]:
            for j in range(2*i,n+1,i):
                L[j] = False
    return [i for i in range(n+1) if L[i]]

Cette fonction retournera la liste des nombres premiers inférieurs ou égaux à son paramètre n. Son principe est simple :

  • On commence par créer une liste de booléens dont les indices sont les entiers compris entre 0 et n. Initialement les valeurs d'indices 0 et 1 valent False, les autres True.

  • On parcourt cette liste à partir de l'indice 2, et si la valeur correspondante est True (i.e. l'indice est un nombre premier) on affecte False à ses multiples.

  • Finalement, on retourne une liste constituée des entiers dont la valeur est True.

Utilisons maintenant notre fonction avec n = 100 , et constatons que l'on retrouve bien la liste précédemment établie "à la main" :

print(eratosthene(100))
[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]
[Note]

L'implémentation précédente pourrait facilement être améliorée, en particulier en traitant d'abord le cas de 2 et de ses multiples, puis en itérant uniquement sur les nombres impairs. Nous laissons le lecteur y réfléchir.

Petit théorème de Fermat

Cette partie sera consacrée au petit théorème de Fermat, qui nous sera fort utile lors de l’étude des algorithmes cryptographiques R.S.A. et El Gamal (voir dernier chapitre de ce cours).

Enoncé et démonstration du théorème

Le théorème qui suit fut énoncé par Pierre de Fermat (1601-1665) en 1640, puis démontré par Leonhard Euler (1707-1783) un siècle plus tard.

Petit théorème de Fermat

Soit p un nombre premier et a un entier naturel non divisible par p.

Alors, a p - 1 1 [ p ] .

Pour bien fixer les idées, présentons de suite un exemple.

Example 1.2. Application du petit théorème de fermat

Montrons que le reste de la division euclidienne de 2 100 par 101 est égal à 1.

En effet, 101 étant un nombre premier et 2 n'étant pas divisible par 101, le petit théorème de Fermat implique que 2 101 - 1 1 [ 101 ] , c'est-à-dire 2 100 1 [ 101 ] .


Ce théorème possède une formulation équivalente, toute aussi utile. On choisit l'une ou l'autre selon le contexte.

Petit théorème de Fermat : formulation équivalente

Soit p un nombre premier et a un entier naturel quelconque.

Alors, a p a [ p ] .

[Note]

La différence entre les deux formulations réside donc dans l'hypothèse de non divisibilité de a par p.

Nous allons à présent vérifier que les deux formulations précédentes sont bien équivalentes.

Démonstration de l'équivalence entre les deux formulations du petit théorème de Fermat

Supposons dans un premier temps que la première formulation soit vérifiée. Considérons p un nombre premier et a un entier naturel quelconque. On distingue alors deux cas selon que p divise ou ne divise pas a :

  • Si p | a , alors p | a p . On a alors a 0 [ p ] et a p 0 [ p ] . Ainsi a p a [ p ] .

  • Si p ne divise pas a, la première formulation s'applique et on a a p - 1 1 [ p ] . Après multiplication par a (règle opératoire des relations de congruence) on obtient bien a p a [ p ] .

Dans les deux cas la seconde formulation est démontrée.

Réciproquement, supposons maintenant que la seconde formulation soit vérifiée. Considérons p un nombre premier et a un entier naturel non divisible par p. Par hypothèse p | ( a p - a ) , ce qui peut se réécrire p | a ( a p - 1 - 1 ) . Puisque p ne divise pas a, le théorème d'Euclide implique que p | ( a p - 1 - 1 ) . D'où a p - 1 1 [ p ] . Q.E.D.

Il ne nous reste plus qu'à démontrer l'une des deux formulations du théorème, ce que nous allons faire avec la première. Cette preuve est plus délicate que celles rencontrées jusqu'à présent, que le lecteur soit attentif.

Démonstration du petit théorème de Fermat (première formulation)

On considère donc p un nombre premier et a un entier naturel non divisible par p.

On commence par montrer que pour tout entier p tel que 1 k p - 1 , le reste de la division euclidienne de ka par p est non nul. Raisonnons par l’absurde : supposons que ce reste soit nul, i.e. que p | k a pour un k tel que 1 k p - 1 . Comme p ne divise pas a, le théorème d’Euclide implique que p | k . Ce qui est impossible car k est inférieur à p.

Montrons ensuite que les restes des divisions euclidiennes de ka et k a par p sont différents, pour k, k tels que 1 k , k p - 1 et k k . Raisonnons là aussi par l’absurde : supposons que k a k a [ p ] pour k, k tels que 1 k , k p - 1 et k k . Cela implique que ( k - k ) a 0 [ p ] . Ainsi p | ( k - k ) a . Comme p ne divise pas a, le théorème d’Euclide implique que p | ( k - k ) . Ce qui est impossible car k - k est inférieur (en valeur absolue) à p - 2 (puisque 1 k , k p - 1 ).

Les deux points précédents impliquent que les nombres a,2a,3a,..., ( p - 1 ) a ont après division euclidienne par p des restes tous différents et non nuls. Ces restes valent donc (dans le désordre) 1,2,3,..., p - 1 .

On a alors a × 2 a × . . . × ( p - 1 ) a 1 × 2 × . . . × ( p - 1 ) [ p ] , ce qui peut se réécrire a p - 1 ( p - 1 ) ! ( p - 1 ) ! [ p ] , ou encore après factorisation ( a p - 1 - 1 ) ( p - 1 ) ! 0 [ p ] .

Ainsi p | ( a p - 1 - 1 ) ( p - 1 ) ! Or p est premier avec ( p - 1 ) ! (aucun diviseur commun ne peut exister) donc d’après le théorème de Gauss p | ( a p - 1 - 1 ) . Ce qui signifie bien sûr que a p - 1 1 [ p ] . Q.E.D.

Exercice

Le petit exercice suivant permettra au lecteur de vérifier sa capacité à bien utiliser le petit théorème de Fermat.

Exercice corrigé

1.1.

Montrer que pour tout entier naturel a, a 13 - a est divisible par 26.

D'après la la seconde formulation du petit théorème de Fermat, a 13 - a est divisible par 13.

D'après ce même résultat, a 2 a [ 2 ] . D'après l'une des régles opératoires sur les congruence a 4 a 2 [ 2 ] , et donc a 4 a [ 2 ] . Cette même règle implique que a 12 a 3 [ 2 ] . Il vient a 13 a 4 [ 2 ] , puis finalement a 13 a [ 2 ] . Ainsi a 13 - a est divisible par 2.

Les entiers 2 et 13 étant premiers entre eux, on conclut alors en utilisant le corollaire du théorème de Gauss (voir le deuxième chapitre du cours).

Factorisation en produit de nombres premiers

Nous allons dans cette partie présenter un théorème souvent appelé théorème fondamental de l’arithmétique de part son importance.

Théorème fondamental de l'arithmétique

Le but du théorème suivant est d’écrire tout nombre entier comme un produit de nombres premiers. Ces derniers apparaîtront alors comme des briques permettant de reconstituer tous les nombres entiers.

Une fois de plus il est l'oeuvre de Carl Friedrich Gauss (1777-1855) et figure dans son fameux "Disquisitiones Arithmeticae".

Théorème

Tout entier a 2 se décompose de manière unique (à l’ordre des facteurs près) sous la forme d’un produit de nombres premiers, i.e.

a = i = 1 r p i α i

où les p i sont des nombres premiers deux à deux distincts et les α i des entiers naturels non nuls.

Démonstration

La démonstration de l'existence se fait par récurrence sur a :

  • Initialisation : pour a = 2 il n'y a rien à démontrer car 2 est un nombre premier.

  • Hérédité : supposons la propriété vérifiée pour tous les entiers inférieurs à un entier a 2 , et montrons la pour a + 1 . D'après le premier théorème de la sous-partie 1.3, a + 1 admet un diviseur premier p. Il existe donc un entier q, avec 1 q < a + 1 , tel que a + 1 = p q . On peut alors appliquer l'hypothèse de récurrence à q, et l'écrire comme produit de nombres premiers. En multipliant ce produit par p, on aura alors la décomposition de a + 1 , ce que l'on souhaitait obtenir.

  • On conclut alors en appliquant le principe de récurrence.

L'unicité se prouve à l'aide du théorème d'Euclide. Nous ne nous y attarderons pas.

La détermination pratique d’une telle décomposition est en général très difficile à obtenir. C’est d'ailleurs à cause de cette difficulté que certains systèmes de cryptographie tels que le R.S.A. sont si efficaces. Nous reviendrons sur ce point dans le dernier chapitre de ce cours.

Une méthode naïve pour obtenir la décomposition d'un entier est de chercher à le diviser successivement par les nombres premiers qui lui sont inférieurs, et ce jusqu'à obtenir un nombre premier.

Example 1.3. Décomposition de 1400 en produits de nombres premiers

On commence par diviser 1400 par 2 autant de fois que possible : on a 1400 = 2 × 700 , 700 = 2 × 350 et 350 = 2 × 175 .

On constate ensuite que 175 n'est pas divisible par 3.

Il est par contre divisible deux fois par 5 : 175 = 5 × 35 et 35 = 5 × 7 .

Le nombre 7 étant premier, la décomposition est terminée : 1400 = 2 3 × 5 2 × 7 .


Algorithme de factorisation

L'algorithme que l'on va présenter dans cette sous-partie reprend la méthode utilisée dans l'exemple précédent.

def factorisation(n):
    L = []
    while n % 2 == 0:
        L.append(2)
        n //= 2
    m = 3
    while m*m <= n:
        if n % m == 0:
            L.append(m)
            n //= m
        else:
            m += 2
    if n > 1:
        L.append(n)
    return L

Cette fonction retournera la liste des nombres premiers constituant la décomposition de son paramètre n. Son principe est simple mais subtil :

  • On commence par diviser n par 2 autant que faire se peut.

  • On fait la même chose avec 3.

  • Grâce au "m += 2" on ne s'occupera ensuite que de la divisibilité par des nombres impairs, ce qui est sensé puisque l'on recherche des diviseurs premiers.

  • On recherche alors la divisibilté par 5, 7 qui sont premiers.

  • Lorsque m sera égal à 9, la condition "n % m == 0" sera nécessairement fausse puisque l'on a testé la divisibilité par 3 auparavant. C'est ce que l'on souhaite car 9 n'est bien sûr pas un nombre premier.

  • On recherche ensuite la divisibilté par 11, 13 qui sont premiers.

  • Lorsque m sera égal à 15, la condition "n % m == 0" sera nécessairement fausse puisque l'on a testé la divisibilité par 3 et 5 auparavant. C'est ce que l'on souhaite car 15 n'est bien sûr pas un nombre premier.

  • etc

  • La dernière condition est nécessaire pour rajouter le dernier facteur à la liste (si celui-ci n'est pas égal à 2). En effet, pour ne pas effectuer d'itérations inutiles, la condition "m*m <= n" arrête la recherche à n . Or puisque l'on met n à jour au fur et à mesure, le dernier facteur est égal à la valeur finale de n.

Utilisons maintenant notre fonction avec n = 1400 , et constatons que l'on retrouve bien la décomposition précédemment établie "à la main" :

print(factorisation(1400))
[2, 2, 2, 5, 5, 7]

L’algorithme précédent est fort naïf et ne marche bien que pour des nombres possédants de petits facteurs premiers. Il en existe de plus efficaces, mais leurs complexités dépassent le cadre de ce cours. Quand on parle ici d’efficacité, il s’agit évidemment de rapidité. La recherche de tels algorithmes est plus que jamais d’actualité.

Applications

On va donner ici des applications du théorème fondamental à des questions de divisibilités.

Le premier résultat permet de savoir à quelle condition un entier en divise un autre.

Théorème : diviseurs d'un entier naturel

Si la décomposition d’un entier naturel a en produit de nombres premiers est

a = i = 1 r p i α i

Alors, un entier naturel b divise a si et seulement si

b = i = 1 r p i β i

où chaque exposant β i vérifie 0 β i α i .

Démonstration

Une simple application du théorème d'Euclide prouve ce résultat.

Ce théorème nous permet facilement de déterminer la liste (et donc le nombre) des diviseurs d'un entier.

Corollaire : nombre de diviseurs d’un entier naturel

Avec les notations du théorème précédent, le nombre n de diviseurs de l’entier a dans est donc

n = i = 1 r ( α i + 1 )

Démonstration

On sait que chaque exposant β i vérifie 0 β i α i , ce qui donne α i + 1 valeurs possibles. D'où le résultat.

Example 1.4. Diviseurs de 1400 (suite de l'exemple précédent)

On avait obtenu 1400 = 2 3 × 5 2 × 7 donc 1400 possède 4 × 3 × 2 = 24 diviseurs.

De plus, ceux-ci seront de la forme 2 m × 5 n × 7 p 0 m 3 , 0 n 2 et 0 p 1 .

On trouve alors 1,2,4,5,7,8,10,14,20,25,28,35,40,50,56,70,100,140,175,200,280,350,700,1400.


Pour conclure ce chapitre, voyons comment utiliser la décomposition en produit de nombres premiers de deux entiers afin de calculer leur PGCD.

Théorème : calcul du PGCD

Si la décomposition de deux entiers naturels a et b en produit de nombres premiers est

a = i = 1 r p i α i et b = i = 1 r p i β i

avec α i , β i éventuellement nuls, alors

PGCD ( a , b ) = i = 1 r p i m i n ( α i , β i )

Example 1.5. Calcul du PGCD de 1400 et 2250

On détermine leur décomposition en produit de nombres premiers : 1400 = 2 3 × 5 2 × 7 et 2250 = 2 1 × 3 2 × 5 3 .

On écrit alors ces deux décompositions avec les mêmes nombres premiers, quitte à avoir des exposants nuls : 1400 = 2 3 × 3 0 × 5 2 × 7 et 2250 = 2 1 × 3 2 × 5 3 × 7 0 .

D'après le théorème précédent on a alors PGCD ( 1400 , 2250 ) = 2 1 × 3 0 × 5 2 × 7 0 = 2 × 5 2 = 50 .


A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels