Déjà plus de
1 million
d'inscrits !
Nombres premiers et petit théorème de Fermat
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde la vidéo
Introduction :
Dans l’ensemble , une place particulière est faite, depuis l’Antiquité, à l’étude des nombres premiers. Ces nombres, qui d’après leur définition ne sont divisibles que par et eux-mêmes, permettent d’obtenir par multiplication tous les nombres entiers.
De nos jours, une grande part de la recherche mathématique s’intéresse à eux, à leur obtention et à leur utilisation, notamment dans le numérique et le codage des données.
Dans une première partie, nous définirons les nombres premiers, et nous apprendrons comment reconnaître qu’un nombre est premier ou non.
Nous verrons, dans une deuxième partie, que tout nombre entier peut être « généré » à partir de nombres premiers.
Dans la dernière partie de ce cours, nous nous intéresserons à un résultat de l’arithmétique, le petit théorème de Fermat, qui a de nombreuses applications.
Nombres premiers
Nous avons déjà abordé les nombres premiers en classe de seconde ; nous allons rappeler les définitions et les premières propriétés de ces nombres.
Définition et exemples
Nombre premier :
Soit .
est un nombre premier lorsqu’il a exactement deux diviseurs entiers naturels distincts : et lui-même.
Donnons quelques conséquences :
Illustrons comment prouver qu’un nombre est premier ou non en recherchant la liste de ses diviseurs.
Soit , avec .
Nous cherchons à savoir si le nombre entier peut être un nombre premier.
Méthodologie :
Pour montrer qu’un nombre n’est pas premier, il suffit de trouver un diviseur de différent de et de lui-même.
Pour trouver d’éventuels diviseurs de , essayons de factoriser cette expression en utilisant la forme canonique d’un polynôme du second degré.
Comme , on a : .
Nous envisageons donc les deux cas suivants :
Les nombres entiers et sont des diviseurs de et sont tous les deux strictement supérieurs à .
Dans cet exemple, nous avons déterminé si un entier pouvait être un nombre premier en recherchant ses diviseurs. Parfois, il n’est pas évident de trouver ces diviseurs.
Dans le paragraphe suivant, nous allons donc utiliser un algorithme pour déterminer si un nombre est premier.
Reconnaître si un nombre est premier
Ce critère de reconnaissance d’un nombre premier a été trouvé dans les travaux d’un mathématicien du XIIIe siècle, Léonard de Pise, connu sous le nom de Fibonacci.
Prenons , avec .
Si n’est pas un nombre premier, alors admet au moins un diviseur premier tel que .
Nous allons démontrer cette propriété.
Soit , un nombre entier qui n’est pas premier.
a donc un diviseur tel que .
Comme divise et divise , alors, par transitivité, divise .
est donc un diviseur de plus petit que et supérieur à , ce qui contredit la définition de .
Nous utiliserons souvent cette propriété dans sa forme contraposée.
Si n’admet aucun diviseur premier inférieur à , alors est un nombre premier.
Prenons un exemple pour illustrer l’utilisation de cette propriété.
Nous voulons savoir si le nombre est premier.
Nous testons alors la divisibilité de par tous les nombres premiers inférieurs à .
Toujours en utilisant cette propriété, nous pouvons également établir la liste des nombres premiers inférieurs à un entier .
Pour déterminer cette liste, on utilise le crible (ou critère) d’Ératosthène, un savant de l’Antiquité, qui a vécu au IIIe s. av. J.-C.
Sa méthode part d’un tableau où sont écrits les premiers nombres entiers supérieurs ou égaux à .
Nous allons illustrer cette méthode avec et déterminer les nombres premiers compris entre et . Ils nous seront utiles plus tard quand nous décomposerons un nombre entier en facteurs premiers.
Nous allons mettre en gris tous les nombres entiers qui ne sont pas premiers ; et encadrer les nombres premiers au fur et à mesure que nous les trouverons.
Pour les reconnaître, nous utilisons le critère de divisibilité : « Un entier est divisible par si et seulement si la somme de ses chiffres est un multiple de ».
Nous avons grisé les multiples des nombres premiers inférieurs ou égaux à ; donc nous avons trouvé tous les nombres de la grille qui ne sont pas premiers.
En particulier, les nombres premiers inférieurs à sont :
Nous avons déterminé l’ensemble des nombres premiers strictement inférieurs à et il ne semble pas y avoir de « schéma » ou de relation évidente entre eux.
Quels sont les autres nombres premiers ? Pouvons-nous tous les déterminer ou déterminer leur place dans ? Nous allons nous intéresser à leur ensemble.
Ensemble des nombres premiers
Il y a une infinité de nombres premiers.
Nous allons démontrer cette propriété ; l’idée de cette démonstration vient d’un autre mathématicien de l’Antiquité, Euclide, dont nous connaissons déjà des travaux en arithmétique, comme l’utilisation des divisions euclidiennes et l’algorithme de recherche d’un .
Leur ensemble, classé par ordre coissant, est .
est strictement supérieur à tous les de l’ensemble des nombres premiers.
On note ce nombre premier :
divise et divise .
Nous ne connaissons donc pas tous les nombres premiers ni comment les obtenir. Des études sont menées sur ces derniers, car leur connaissance permet d’obtenir des méthodes de codage et de chiffrement des données.
Pour le comprendre, nous devons d’abord nous intéresser au lien entre les nombres premiers et les autres nombres entiers.
Décomposition d’un nombre entier en facteurs premiers
En seconde, nous avons déjà vu qu’un nombre entier non premier pouvait s’écrire comme un produit de nombres premiers.
Par exemple, si nous considérons le nombre , il peut s’écrire ainsi :
C’est un produit des nombres premiers , et .
Cette décomposition est possible pour chacun des nombres entiers non premiers. C’est ce que nous allons voir avec les propriétés ci-dessous.
Existence et unicité de la décomposition
Soit , un nombre entier non premier.
est le produit de nombres premiers.
Il existe des nombres premiers , , …, distincts et des entiers , , …, appartenant à tels que :
Cette décomposition de en produit de facteurs premiers est unique.
Dans l’exemple ci-dessus, , les nombres premiers sont , et , et les nombres , , valent respectivement , et .
Décomposition en produit de facteurs premiers :
Soit un nombre entier naturel non premier.
Nous allons démontrer l’existence de la décomposition en facteurs premiers. Le premier à avoir démontré cette propriété est Euclide.
Soit
Cela signifie que la décomposition s’arrête et nous arrivons à :
Au dernier
Cela donne donc la décomposition :
Remarque :
Si
Ainsi, si
Ces deux propriétés – existence et unicité – de la décomposition en produit de facteurs premiers sont connues comme le théorème fondamental de l’arithmétique.
Il stipule en effet que les nombres premiers « génèrent » par produit l’ensemble des nombres entiers naturels.
Pour trouver la décomposition en facteurs premiers de
Méthodologie :
Pour cela, nous pouvons nous aider des critères de divisibilité et de la liste des diviseurs premiers inférieurs à
Prenons un exemple pour illustrer cette méthode, qui est un algorithme que nous pourrions programmer.
Nous voulons décomposer
Pour schématiser ces divisions successives, nous pouvons les noter dans un tableau.
Quotient | Division par |
Nous allons maintenant nous intéresser à l’ensemble des diviseurs d’un nombre entier, à partir de cette décomposition.
Diviseurs d’un nombre entier naturel
Reprenons l’exemple de la décomposition de
Si
Comme la décomposition de
Il y a
En nous appuyant sur cet exemple, nous en déduisons la forme des diviseurs d’un nombre
Soit
Les diviseurs positifs de
Prenons un exemple pour illustrer cette propriété.
Nous avons vu que
Les diviseurs de
Cette propriété va nous permettre également de résoudre certaines équations comme dans l’exemple ci-dessous.
Nous voulons résoudre dans
Les nombres entiers
Nous cherchons dans cette liste un entier
Enfin, une des applications du théorème fondamental de l’arithmétique est de trouver le
Application :
Nous retrouvons la propriété sur le
Soit
Nous cherchons
Nous avons établi que :
Les facteurs premiers communs aux deux décompositions sont
Nous nous sommes intéressés à la décomposition des nombres entiers en facteurs de nombres premiers. Ces algorithmes deviennent ardus quand le nombre entier est très grand, même avec les ordinateurs d’aujourd’hui.
Nous allons maintenant examiner un théorème important de l’arithmétique qui permet notamment de déterminer la divisibilité de très grands nombres par des nombres premiers.
Petit théorème de Fermat
Pierre de Fermat est un mathématicien français qui vécut au XVIIesiècle et travailla surtout sur les nombres. Il écrivit de nombreuses propriétés arithmétiques, mais ne fournit pas toujours de démonstrations écrites.
Certaines conjectures sont en en cours d’analyse de nos jours, certaines ont été prouvées ou contredites plusieurs siècles plus tard. Le petit théorème de Fermat a notamment été démontré par le mathématicien Léonard Euler, qui vécut au XVIIIe siècle.
Petit théorème de Fermat
Nous admettons le résultat suivant.
Soit
Alors
Prenons un exemple d’application directe de ce théorème.
Nous cherchons le reste dans la division euclidienne de
Nous pouvons donc appliquer le petit théorème de Fermat et déduire que :
Ce théorème permet de résoudre des équations à congruence avec de grands nombres. Pour nous en convaincre, prenons un autre exemple.
Nous voulons résoudre l’équation
Nous effectuons la division euclidienne de
Ainsi, nous pouvons appliquer le petit théorème de Fermat à
Nous avons donc :
Nous utilisons, comme dans le cours sur la divisibilité dans
Si
Nous allons maintenant procéder comme nous l’avons appris dans le cours sur la congruence.
$0$ | $1$ | $2$ | $3$ | ||||||||
$0$ | $1$ | $1$ |
Ces exemples illustrent le cas où le nombre premier
Nous disposons également d’un corollaire qui s’applique à n’importe quel entier naturel
Corollaire du petit théorème de Fermat
Soit
Alors
Soit
L’intérêt de ce corollaire peut être énoncé ainsi : un entier
Prenons un exemple d’application de cette propriété.
Nous cherchons à montrer que
La congruence est compatible avec l’addition, donc :
Cet exemple prouve l’efficacité du petit théorème de Fermat et de son corollaire quand il s’agit de déterminer la divisibilité ou la congruence de très grands nombres par des nombres premiers.
Conclusion :
Dans ce cours, nous avons abordé quelques notions du vaste champ d’étude des nombres premiers : leur définition, quelques algorithmes pour les reconnaître et quelques propriétés fondamentales.
Des applications nombreuses et actuelles utilisent les grands nombres premiers, qui ne sont pas encore très connus, pour chiffrer ou déchiffrer des données, notamment dans le commerce électronique ou la cryptographie ; c’est pourquoi l’arithmétique reste une branche active de la recherche en mathématiques.