premiers, nombres - mathématiques.

premiers, nombres - mathématiques. 1 PRÉSENTATION premiers, nombres, nombres entiers naturels p admettant exactement deux diviseurs : 1 et eux-mêmes. Ainsi, par définition, le nombre 1 n'est pas premier puisqu'il n'admet qu'un seul diviseur. Les dix plus petits nombres premiers positifs sont ainsi : 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29. Tout nombre entier se décompose sous la forme unique d'un produit de facteurs premiers. Par exemple : 60 = 2 × 2 × 3 × 5 De manière générale, la définition des nombres premiers est restreinte aux entiers naturels. Toutefois, elle peut être étendue aux entiers relatifs. Dans ce cas, un nombre premier relatif est un nombre entier relatif p (différent de 1) qui n'est divisible que par 1, - 1, p et - p. 2 Au CRIBLE D'ÉRATOSTHÈNE IIIe siècle av. J.-C., le Grec Ératosthène met au point une méthode, appelée crible d'Ératosthène, permettant de déterminer les nombres premiers inférieurs à un entier naturel donné n. Cette méthode consiste, dans un premier temps, à écrire la liste de tous les entiers naturels compris entre 2 et n (le nombre 1 n'étant pas premier par définition). On entoure le nombre 2 (premier nombre de la liste), qui est un nombre premier, et on élimine tous les multiples de 2. Puis on fait de même avec 3, qui est aussi premier, et ainsi de suite jusqu'à n. Les nombres non éliminés sont les nombres premiers inférieurs à n. Cette méthode est rapidement fastidieuse pour un nombre n élevé, mais, à ce jour, aucune formule simple n'a été découverte pour répertorier les nombres premiers. 3 UN ENSEMBLE INFINI Dans le neuvième livre des Éléments, le mathématicien grec Euclide fournit une élégante démonstration prouvant que l'ensemble des nombres premiers est infini. Il s'agit d'une démonstration par l'absurde : supposons que l'ensemble des nombres premiers soit fini, et appelons p le plus grand nombre premier de cet ensemble. Considérons le produit q = [1 × 2 × 3 × ...× (p - 1) × p] + 1, qui est donc le produit de tous les entiers de 1 à p, augmenté d'une unité. Ce nombre q peut être décomposé en produit de facteurs premiers. Soit ? l'un de ces facteurs non égal à 1. Comme ? < p, ? est donc un diviseur du produit [1 × 2 × 3 × ... × (p - 1) × p]. Mais, par ailleurs, ? est aussi un diviseur de ce produit augmenté d'une unité puisque ? est un facteur de q. Or, deux entiers consécutifs ne peuvent avoir de diviseur commun excepté 1. On aboutit par conséquent à une contradiction : l'hypothèse de départ était fausse, l'ensemble des nombres premiers est infini. Bien que leur nombre soit infini, les nombres premiers deviennent de plus en plus rares au fur et à mesure que l'on avance dans l'ensemble des entiers. En effet, on a démontré que pour de grandes valeurs d'un entier n, le total des nombres premiers positifs inférieurs à n est approximativement égal à n / ln n (ln n désignant le logarithme népérien de n). Ainsi, les nombres premiers représentent environ 22 p. 100 des nombres compris entre 1 et 100, 15 p. 100 des nombres compris entre 1 et 1 000, et 7 p. 100 des nombres compris entre 1 et 1 million. En 2005, le plus grand nombre premier répertorié est 225 964 951 - 1, soit un nombre à 7 816 230 chiffres. Il a été découvert par Martin Nowak, un médecin allemand participant au programme du GIMPS (Great Internet Mersenne Prime Search) -- un projet de calcul partagé qui utilise des ordinateurs en réseau pour effectuer les longs calculs nécessaires à la découverte de ce type particulier de nombres premiers, dits de Mersenne (du nom du religieux savant Marin Mersenne, de formule générale Mp = 2p - 1, où p est aussi un nombre premier). Le GIMPS est sur la bonne voie pour trouver un nombre premier de plus de 10 millions de chiffres et décrocher ainsi la prime de 100 000 dollars promise par l'Electronic Frontier Foundation (EFF, une association américaine de défense et de promotion de l'utilisation d'Internet) pour le premier nombre premier de cette taille. L'EFF prévoit également une prime de 150 000 dollars pour la découverte du premier nombre premier de plus de 100 millions de chiffres décimaux, et une prime de 250 000 dollars pour le premier nombre premier de plus d'un milliard de chiffres décimaux. 4 NOMBRES PREMIERS ENTRE EUX On dit que deux entiers naturels sont premiers entre eux si leur seul diviseur commun est égal à 1 (de même, deux entiers relatifs sont premiers entre eux si leurs seuls diviseurs communs sont 1 et - 1). Lorsque deux entiers relatifs a et b sont premiers entre eux, on démontre qu'il existe deux entiers relatifs u et v, premiers entre eux, tels que a.u + b.v = 1. Cette égalité est connue sous le nom d'égalité de Bézout, du nom du mathématicien français Étienne Bézout (1730-1783). 5 HYPOTHÈSES ET RÉSULTATS 5.1 Nombres premiers jumeaux Deux nombres premiers dont la différence vaut 2 sont appelés nombres premiers jumeaux, comme 5 et 7, 17 et 19, 101 et 103. Jusqu'à présent, les mathématiciens ne sont pas parvenus à découvrir si l'ensemble des nombres premiers jumeaux est infini. 5.2 Conjectures de Goldbach En 1742, le mathématicien russe Christian Goldbach énonce sans démonstration que tout entier pair est la somme de deux nombres premiers. Ainsi, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 20 = 3 + 17, 100 = 3 + 97, etc. Pour le moment, cette hypothèse n'a pas été prouvée. Goldbach affirme également que tout nombre est la somme de trois nombres premiers. Bien que cette assertion n'ait pas été démontrée dans le cas général, le mathématicien soviétique Ivan Vinogradov prouve en 1937 qu'elle est vraie dans le cas d'entiers impairs, autres que 3 et 5. 5.3 Théorème de Wilson Énoncé en 1770 par le mathématicien anglais John Wilson, et démontré en 1773 par le Français Joseph Lagrange, le théorème de Wilson est une condition nécessaire et suffisante pour tester la primalité d'un nombre : si p est premier, alors il divise l'expression 1 + (p - 1) ! = 1 + [ 2 × 3 × ...× (p - 2) × (p - 1)]. 6 APPLICATIONS Les nombres premiers font actuellement l'objet de recherches mettant en oeuvre la puissance de calcul des supercalculateurs. On cherche notamment à trouver de très grands nombres premiers. Leur produit donne un nombre dont il est très difficile pour quiconque de retrouver les facteurs premiers qui l'ont engendré. Cette propriété est utilisée dans les systèmes de cryptographie dite à clef publique, aujourd'hui indispensables pour les transactions bancaires et le commerce électronique. Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. Tous droits réservés.