Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Nombres premiers entre eux
Résumé
vignette|Le segment ne passe par aucun point du réseau (hormis les points à ses extrémités), ce qui montre que 4 et 9 sont premiers entre eux.
En mathématiques, on dit que deux entiers a et b sont premiers entre eux, que a est premier avec b ou premier à b ou encore que a et b sont copremiers (ou encore étrangers) si leur plus grand commun diviseur est égal à 1 ; en d'autres termes, s'ils n'ont aucun diviseur autre que 1 et –1 en commun. De manière équivalente, ils sont premiers entre eux s'ils n'ont aucun facteur premier en commun.
Par exemple, 6 et 35 sont premiers entre eux, mais 6 et 27 ne le sont pas parce qu'ils sont tous les deux divisibles par 3. Le nombre 1 est premier avec tout entier, tandis que 0 est uniquement premier avec 1 et –1.
Cette notion a été introduite dans le livre VII des Éléments d'Euclide.
Des notations standard pour deux entiers a et b premiers entre eux sont : pgcd(a, b) = 1 ou a∧b = 1. Ronald Graham, Donald Knuth et Oren Patashnik ont aussi proposé la notation .
Un moyen rapide pour déterminer si deux nombres entiers sont premiers entre eux est l'algorithme d'Euclide, ou ses versions plus rapides telles que l'algorithme du PGCD binaire ou l'.
Le nombre d'entiers premiers avec un entier positif n et compris entre 1 et n est égal à φ(n), où φ est la fonction phi d'Euler.
Dans ce qui suit, a et b désignent deux entiers relatifs.
Si a est premier avec divers autres entiers alors il est premier avec leur produit, puisque tout diviseur non trivial de ce produit doit diviser l'un des entiers, et donc ne pas diviser a.
Si a est premier avec b, a + bc est premier avec b quel que soit l'entier c. En effet, pgcd(b, a + bc) = pgcd(b, a).
Si a est premier avec b, alors a + b est premier avec a et b : ce n'est guère que le résultat ci-dessus appliqué à c = 1, et appliqué à nouveau en inversant les rôles de a et b.
Un nombre p est premier si, et seulement si, il est premier avec tout nombre qu'il ne divise pas.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (36)