Test de primalitévignette|Le 39e nombre premier de Mersenne découvert à ce jour pour un article sur la primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Le test le plus simple est celui des divisions successives : pour tester N, on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N-1. Si la réponse est négative, alors N est premier, sinon il est composé.
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.
Nombres premiers jumeauxEn mathématiques, deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2. Hormis pour le couple (2, 3), cet écart entre nombres premiers de 2 est le plus petit possible. Les plus petits nombres premiers jumeaux sont 3 et 5, 5 et 7, 11 et 13. En , les plus grands nombres premiers jumeaux connus, découverts en 2016 dans le cadre du projet de calcul distribué PrimeGrid, sont × 2 ± 1 ; ils possèdent chiffres en écriture décimale.
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 .
Éléments (Euclide)Les Éléments (en grec ancien / stoïkheïa) est un traité mathématique et géométrique, constitué de 13 livres organisés thématiquement, probablement écrit par le mathématicien grec Euclide vers Il comprend une collection de définitions, axiomes, théorèmes et leur démonstration sur les sujets de la géométrie euclidienne et de la théorie des nombres primitifs. L'ouvrage est le plus ancien exemple connu d'un traitement axiomatique et systématique de la géométrie et son influence sur le développement de la logique et de la science occidentale est fondamentale.
Nombre de Mersenne premiervignette|droite|Le moine français Marin Mersenne (1588-1648) En mathématiques et plus précisément en arithmétique, un nombre de Mersenne est un nombre de la forme 2 − 1 (souvent noté ), où est un entier naturel non nul ; un nombre de Mersenne premier (ou nombre premier de Mersenne) est donc un nombre premier de cette forme. Ces nombres doivent leur nom au religieux érudit et mathématicien français du Marin Mersenne ; mais, près de auparavant, Euclide les utilisait déjà pour étudier les nombres parfaits.
Théorie des criblesEn mathématiques, la théorie des cribles est une partie de la théorie des nombres ayant pour but d'estimer, à défaut de dénombrer, les cardinaux de sous-ensembles (éventuellement infinis) de N en approchant la fonction indicatrice du sous-ensemble considéré. Cette technique a pour origine le crible d'Ératosthène, et dans ce cas, le but était d'étudier l'ensemble des nombres premiers. Un des nombreux résultats que l'on doit aux cribles a été découvert par Viggo Brun en 1919.
Arithmétique modulaireEn mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l’étude du reste obtenu par une division euclidienne. L'idée de base de l'arithmétique modulaire est de travailler non sur les nombres eux-mêmes, mais sur les restes de leur division par quelque chose. Quand on fait par exemple une preuve par neuf à l'école primaire, on effectue un peu d'arithmétique modulaire sans le savoir : le diviseur est alors le nombre 9.
Décomposition en produit de facteurs premiersvignette|Décomposition du nombre 864 en facteurs premiers En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 3 × 5, soit 3 × 3 × 5.
Formules pour les nombres premiersEn mathématiques, la recherche de formules exactes donnant tous les nombres premiers, certaines familles de nombres premiers ou le nombre premier s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les principaux résultats obtenus. L'espoir d'obtenir une formule exacte et simple donnant le n-ième nombre premier p, ou le nombre π(n) de nombres premiers inférieurs ou égaux à n, s'est très tôt heurté à l'extrême irrégularité de leur répartition, ce qui a amené à se contenter d'objectifs moins ambitieux.
Nombres premiers sexyEn mathématiques, un couple de nombres premiers sexy (ou nombres premiers sexys) est un couple de nombres premiers dont la différence est 6 (autrement dit, un couple de la forme (p, p + 6) où p et p + 6 sont des nombres premiers). C'est le cas, par exemple, des nombres 5 et 11. Certains de ces nombres premiers sont consécutifs, par exemple 23 et 29 sont premiers et il n'y a pas de nombre premier entre eux deux. Le terme « sexy » est un jeu de mots fondé sur le mot latin pour « six » : sex.
Entier de Gaussthumb|Carl Friedrich Gauss. En mathématiques, et plus précisément, en théorie algébrique des nombres, un entier de Gauss est un nombre complexe dont la partie réelle et la partie imaginaire sont des entiers relatifs. Il s'agit formellement d'un élément de l'anneau des entiers quadratiques de l'extension quadratique des rationnels de Gauss L'ensemble des entiers de Gauss possède une structure forte. Comme tous les ensembles d'entiers algébriques, muni de l'addition et de la multiplication ordinaire des nombres complexes, il forme un anneau intègre, généralement noté , désignant ici l'unité imaginaire.
Crible quadratiqueL'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.
Safe and Sophie Germain primesIn number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes are named after French mathematician Sophie Germain, who used them in her investigations of Fermat's Last Theorem. One attempt by Germain to prove Fermat’s Last Theorem was to let p be a prime number of the form 8k + 7 and to let n = p – 1.
ArithmétiqueL'arithmétique est la branche des mathématiques qui étudie les nombres entiers naturels , relatifs et rationnels , voire réels , ainsi que leurs relations et propriétés, en lien avec quelques opérations élémentaires : addition (+), soustraction (−), multiplication (×), division (÷, /, ou :), puissance et racine (). Le terme inclut parfois d'autres concepts de la théorie des nombres. Le mot arithmétique vient du grec ancien , « nombre ». L’origine de l'arithmétique semble être une invention phénicienne.
Théorème de Pythagorethumb|right|alt=Triangle rectangle et relation algébrique entre les longueurs de ses côtés.|Relation entre les longueurs des côtés dans un triangle rectangle. Le théorème de Pythagore est un théorème de géométrie euclidienne qui met en relation les longueurs des côtés dans un triangle rectangle. Il s'énonce fréquemment sous la forme suivante : Si un triangle est rectangle, le carré de la longueur de l’hypoténuse (ou côté opposé à l'angle droit) est égal à la somme des carrés des longueurs des deux autres côtés.
Géométrie euclidienneLa géométrie euclidienne commence avec les Éléments d'Euclide, qui est à la fois une somme des connaissances géométriques de l'époque et une tentative de formalisation mathématique de ces connaissances. Les notions de droite, de plan, de longueur, d'aire y sont exposées et forment le support des cours de géométrie élémentaire. La conception de la géométrie est intimement liée à la vision de l'espace physique ambiant au sens classique du terme.
Entier relatifEn mathématiques, un entier relatif, un entier rationnel ou simplement un nombre entier est un nombre qui se présente comme un entier naturel auquel on a adjoint un signe positif ou négatif indiquant sa position par rapport à 0 sur un axe orienté. Les entiers positifs (supérieurs à zéro) s'identifient aux entiers naturels : 0, 1, 2, 3... tandis que les entiers négatifs sont leurs opposés : 0, −1, −2, −3... L'entier 0 lui-même est donc le seul nombre à la fois positif et négatif.
