Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Primes: Théorème fondamental et tamis d'Eratosthène

Dans cours

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

Description

Cette séance de cours couvre la définition des nombres premiers et des composites, le théorème fondamental de l'arithmétique indiquant que tout entier supérieur à 1 peut être écrit comme un produit de nombres premiers, la preuve de ce théorème en utilisant une induction forte, la division d'essai pour les entiers composites, le tamis d'Eratosthène pour trouver des nombres premiers, et le théorème d'Euclide prouvant l'infinité des nombres premiers.

Enseignant·e

Karl Aberer

Co-Founder of LinkAlong Sarl, 2017.Vice-president EPFL for Information Systems, 2012 –2016.Director of the Swiss National Centre for Mobile Information and Communication Systems NCCR MICS (mics.ch), 2005 -2012.Member of the Swiss Research and Technology Council SWTR, consulting the Swiss Federal government, 2004 - 2011.

Source officielle

Proximité ontologique

Mathématiques

Théorie des nombres: Théorie des nombres

Concepts associés (32)

Théorème fondamental de l'arithmétique

En 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.

Nombre premier

vignette|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.

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é.

Nombres premiers jumeaux

En 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.

Théorème d'Euclide sur les nombres premiers

En arithmétique, le théorème d'Euclide sur les nombres premiers affirme qu'il existe une infinité de nombres premiers. Ce résultat est énoncé et démontré dans les Éléments d'Euclide, c'est la proposition 20 du livre IX. Il y prend cependant une forme différente : « les nombres premiers sont plus nombreux que n'importe quelle multitude de nombres premiers proposée », plus compatible avec la conception de l'infini de l'auteur. D'autres preuves ont ensuite été proposées, notamment par Euler.

Afficher plus

Séances de cours associées (29)

Théorie des nombres : Primes

Couvre la définition des nombres premiers, le théorème fondamental de l'arithmétique et le théorème d'Euclide.

Algèbre élémentaire: ensembles numériques

Explore les concepts d'algèbre élémentaire liés aux ensembles numériques et aux nombres premiers, y compris la factorisation et les propriétés uniques.

Théorie des nombres : concepts fondamentaux

Couvre l'addition binaire, les nombres premiers et le tamis d'Eratosthène en théorie des nombres.

Tests de nombres premiers et de primalité

Couvre les nombres premiers, la cryptographie RSA et les tests de primalité, y compris le théorème des restes chinois et le test de Miller-Rabin.

Nombres primaires : Théorème d'Euclid

Explore les premiers nombres et le théorème d'Euclid à travers une preuve par contradiction.

Afficher plus

Concepts associés (32)

Théorème fondamental de l'arithmétique

Nombre premier

Test de primalité

Nombres premiers jumeaux

Théorème d'Euclide sur les nombres premiers

Afficher plus