Théorème fondamental de l'arithmétiqueEn mathématiques, et en particulier en arithmétique élémentaire, le théorème fondamental de l'arithmétique ou théorème de décomposition en produit de facteurs premiers s'énonce ainsi : tout entier strictement positif peut être écrit comme un produit de nombres premiers d'une unique façon, à l'ordre près des facteurs. Par exemple, nous pouvons écrire que : = 2 × 3 × 17 ou encore = 2 × 3 × 5 et il n'existe aucune autre factorisation de ou sous forme de produits de nombres premiers, excepté par réarrangement des facteurs ci-dessus.
Crible d'AtkinLe crible d'Atkin est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est une version améliorée du crible d'Ératosthène, il fut créé en 1999 par A. O. L. Atkin et Daniel J. Bernstein. Le crible d'Ératosthène consiste à trouver les valeurs pouvant se réduire à la forme quadratique binaire réduite x⋅y (produit de deux entiers strictement supérieurs à 1). Le crible d'Atkin consiste lui à dénombrer les valeurs d'une forme quadratique binaire non-réduite.
Crible de SundaramLe crible de Sundaram permet de lister les entiers naturels impairs composés grâce à des suites arithmétiques placées en colonnes. Son intérêt est qu'on peut en déduire, par passage au complémentaire, l'ensemble des nombres premiers. S. P. Sundaram était un mathématicien indien originaire de la ville de Sathyamangalan dans l'état du Tamil Nadu. La méthode et le tableau qu'il publia en 1934 donnaient toutes les valeurs telles que ne soit pas premier. Une méthode algorithmique de cette approche offre directement les valeurs des nombres premiers impairs.
Lemme d'Euclidevignette|Le lemme d'Euclide est tiré des Éléments, ouvrage fondateur des mathématiques occidentales. En mathématiques, le lemme d'Euclide est un résultat d'arithmétique élémentaire sur la divisibilité qui correspond à la Proposition 32 du Livre VII des Éléments d'Euclide. Il s'énonce ainsi : Une généralisation est : Formellement : si a|bc et PGCD(a, b) = 1, alors a|c. Dans le traité de Gauss, les Disquisitiones arithmeticae, l'énoncé du lemme d'Euclide constitue la proposition 14 (section 2), qu'il utilise pour prouver l'unicité de la décomposition en produit de facteurs premiers d'un entier (théorème 16), admettant l'existence comme .
Nombre premiervignette|Nombres naturels de zéro à cent. Les nombres premiers sont marqués en rouge. vignette|Le nombre 7 est premier car il admet exactement deux diviseurs positifs distincts. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs. Ces deux diviseurs sont 1 et le nombre considéré, puisque tout nombre a pour diviseurs 1 et lui-même (comme le montre l’égalité n = 1 × n), les nombres premiers étant ceux qui ne possèdent pas d'autre diviseur.
