Nombres premiers et arithmétique

Un nombre premier est un entier naturel supérieur ou égal à 2 qui possède exactement deux diviseurs positifs : 1 et lui-même. Le nombre 1 n’est pas premier, car il n’a qu’un diviseur positif. Le nombre 2 est le seul premier pair : tout autre entier pair supérieur à 2 est divisible par 2 et possède donc un diviseur supplémentaire. Un entier supérieur ou égal à 2 qui n’est pas premier est dit composé.

Pour tester la primalité d’un entier N, il suffit de rechercher un diviseur premier inférieur ou égal à √N. En effet, si N = ab avec 1 < a ≤ b, alors a² ≤ N, donc a ≤ √N. L’entier a possède lui-même au moins un diviseur premier. Si aucun nombre premier jusqu’à cette borne ne divise N, N ne peut pas être composé. La borne doit être incluse : pour N = 49, le diviseur 7 est exactement sa racine carrée.

Le crible d’Ératosthène dresse une liste de premiers jusqu’à une borne. On conserve 2 puis on élimine ses multiples supérieurs à 2 ; on conserve ensuite le premier entier non éliminé et on barre ses multiples. Il suffit de poursuivre avec les premiers inférieurs ou égaux à la racine carrée de la borne. Tout composé a alors été éliminé. Le crible produit une liste ; un test de divisibilité examine un nombre donné.

Tout entier N supérieur ou égal à 2 s’écrit comme produit de nombres premiers. L’existence se comprend par une descente : si N n’est pas premier, on le décompose en facteurs plus petits et on recommence avec ceux qui ne sont pas premiers. Les entiers positifs décroissent au cours de cette recherche ; elle ne peut pas continuer indéfiniment. Les facteurs finaux sont donc tous premiers.

La décomposition est unique à l’ordre des facteurs près. L’idée décisive est le lemme suivant : si un premier p divise un produit ab, alors p divise a ou p divise b. Si p ne divise pas a, leur PGCD vaut 1, donc Gauss impose p | b. En appliquant ce résultat à deux décompositions, un premier de la première apparaît dans la seconde. On le simplifie et on recommence. L’unicité permet de comparer les exposants des mêmes premiers.

Écrire N = p₁^α₁ × … × pᵣ^αᵣ, avec des premiers distincts et des exposants positifs, décrit tous ses diviseurs positifs. Chaque diviseur choisit, pour pᵢ, un exposant compris entre 0 et αᵢ. Il y a donc (α₁ + 1)…(αᵣ + 1) diviseurs positifs. Un carré parfait possède uniquement des exposants pairs ; réciproquement, des exposants tous pairs permettent de prendre leur moitié pour construire sa racine carrée entière.

Supposons qu’il n’existe qu’un nombre fini de nombres premiers, notés p₁, …, pᵣ. Formons N = p₁…pᵣ + 1. Cet entier est supérieur à 1, donc il possède un diviseur premier q. Aucun pᵢ ne peut diviser N, car N laisse un reste 1 lorsqu’on le divise par pᵢ. Ainsi q est un premier absent de la liste supposée complète : contradiction. L’ensemble des nombres premiers est donc infini.

Cette preuve ne prétend pas que N est lui-même premier. C’est l’une de ses forces : même si N est composé, un de ses diviseurs premiers suffit à contredire la liste. Par exemple 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509. L’exemple rappelle qu’une construction adaptée à une preuve d’existence ne donne pas nécessairement une formule qui produit toujours un nombre premier.

La distinction entre conjecture et théorème est importante en arithmétique. Observer de nombreux premiers dans une suite ne prouve pas que la suite en contient toujours. Un seul contre-exemple détruit une affirmation universelle ; des essais favorables ne la démontrent pas. Lorsque le calcul devient long, on conserve donc une trace des divisions réellement effectuées et on indique exactement ce qu’elles permettent de conclure.

Si p est premier et si a est un entier non divisible par p, le petit théorème de Fermat affirme a^(p−1) ≡ 1 [p]. Une autre formulation, valable pour tout entier a, est aᵖ ≡ a [p]. La condition de primalité de p est essentielle. Dans la première formulation, la condition p ne divise pas a l’est également : une base multiple de p donne un reste nul, pas un reste 1.

Voici une justification de la première formulation. Les restes non nuls de a, 2a, …, (p − 1)a modulo p sont tous distincts : si ar ≡ as, alors p divise a(r − s), et Gauss donne p | r − s. Comme r et s sont entre 1 et p − 1, ils sont égaux. Ces restes sont donc ceux de 1, 2, …, p − 1 dans un autre ordre. Leur produit donne a^(p−1)(p − 1) ! ≡ (p − 1) ! [p]. Ce dernier facteur est premier avec p ; on peut l’annuler grâce à un inverse.

Le théorème n’a pas de réciproque générale. Par exemple 341 = 11 × 31 est composé, mais 2¹⁰ = 1024 ≡ 1 [341], donc 2³⁴⁰ ≡ 1 [341]. Un test de Fermat défavorable prouve qu’un entier est composé si ses hypothèses sont correctement examinées ; un résultat favorable pour une base ne prouve pas qu’il est premier. Il faut distinguer un témoin de composition d’un certificat de primalité.

Erreurs fréquentes : classer 1 parmi les premiers ; arrêter un test avant la racine carrée ; confondre premiers et premiers entre eux ; croire que Fermat prouve la primalité. Pour éviter ces erreurs, associe à chaque théorème une liste de ses hypothèses et une conclusion précise. Un outil numérique aide à expérimenter, mais la rédaction explique pourquoi la recherche est exhaustive.

Pour poursuivre, ouvre S’entraîner dans /exercices. Compare ensuite deux preuves d’une même divisibilité, l’une utilisant la décomposition et l’autre une congruence. Le choix de méthode dépend de la question : les facteurs éclairent les diviseurs, tandis que les congruences éclairent les restes.