Divisibilité et nombres premiers
La divisibilité, le plus grand commun diviseur et les nombres premiers constituent le fondement de la théorie des nombres : tout entier est construit multiplicativement à partir de nombres premiers, et sa structure multiplicative régit presque tous les résultats ultérieurs.
Definition
Un entier a divise b si b est égal à a multiplié par un entier ; un nombre premier est un entier supérieur à un dont les seuls diviseurs positifs sont un et lui-même. La divisibilité et les nombres premiers concernent la décomposition multiplicative des entiers et les briques élémentaires irréductibles de cette décomposition.
Scope
Ce sujet aborde la relation de divisibilité sur les entiers, l'algorithme de division, les plus grands communs diviseurs et les plus petits communs multiples calculés via l'algorithme d'Euclide, l'identité de Bézout, le lemme d'Euclide, le théorème fondamental de l'arithmétique, ainsi que la théorie élémentaire des nombres premiers — leur infinitude, les heuristiques de leur distribution et leur primalité.
Core questions
- Comment l'algorithme d'Euclide calcule-t-il les plus grands communs diviseurs et produit-il l'identité de Bézout ?
- Pourquoi le lemme d'Euclide impose-t-il l'unicité de la factorisation en nombres premiers ?
- Comment peut-on prouver qu'il existe une infinité de nombres premiers, et que révèlent de telles preuves ?
- Comment les nombres premiers sont-ils distribués parmi les entiers, et comment la primalité est-elle décidée en pratique ?
Key theories
- Algorithme de division et algorithme d'Euclide
- Tout entier divisé par un entier positif donne un quotient et un reste uniques ; l'itération de ce processus donne le plus grand commun diviseur et, par substitution inverse, des entiers l'exprimant comme une combinaison linéaire (identité de Bézout).
- Théorème fondamental de l'arithmétique
- Tout entier supérieur à un est un produit de nombres premiers unique à l'ordre près ; le lemme d'Euclide (un nombre premier divisant un produit divise un facteur) est l'étape clé.
- Infinitude des nombres premiers
- L'argument classique d'Euclide montre qu'aucune liste finie de nombres premiers n'est complète ; la formule du produit d'Euler pour la fonction zêta fournit une preuve analytique et quantifie la densité des nombres premiers par la divergence de la somme des inverses des nombres premiers.
Clinical relevance
La factorisation rapide et les tests de primalité sont fondamentaux pour la cryptographie : la sécurité de RSA repose sur la difficulté de factoriser de grands produits de deux nombres premiers, tandis que des tests de primalité efficaces (tels que Miller-Rabin) rendent la génération de clés pratique.
History
Les Éléments d'Euclide (vers 300 av. J.-C.) contenaient déjà l'algorithme d'Euclide, le lemme d'Euclide et la preuve que les nombres premiers sont infinis. Le crible d'Ératosthène a fourni la première méthode systématique pour lister les nombres premiers, et les travaux des XVIIIe et XIXe siècles d'Euler, Legendre et Gauss ont reformulé la distribution des nombres premiers comme un problème quantitatif.
Key figures
- Euclid
- Eratosthenes
- Leonhard Euler
- Etienne Bezout
Related topics
Seminal works
- hardyWright2008
Frequently asked questions
- Un est-il un nombre premier ?
- Non. Un est exclu par définition afin que la factorisation en nombres premiers soit unique ; si un était considéré comme premier, chaque nombre aurait une infinité de factorisations.
- À quoi sert l'identité de Bézout ?
- Elle stipule que le plus grand commun diviseur de deux entiers est une combinaison linéaire entière de ceux-ci, ce qui constitue la base du calcul des inverses modulaires et de la résolution des équations diophantiennes linéaires.