Les nombres premiers
Dans une boulangerie, on veut ranger 143 croissants en piles de même hauteur, avec plus d'un croissant par pile et plusieurs piles. Est-ce possible ? Tout dépend de la nature du nombre 143 : est-il premier ou non ? Tu auras la réponse à la fin de la page.
Nombres premiers et crible d'Ératosthène
Exemples : $7$ est premier (diviseurs : $1$ et $7$). $12$ est composé (diviseurs : $1, 2, 3, 4, 6, 12$).
Pour trouver tous les nombres premiers jusqu'à $100$, on utilise le crible d'Ératosthène : on écrit les nombres, puis on barre les multiples de $2$ (sauf $2$), les multiples de $3$ (sauf $3$), de $5$, de $7$… Les nombres qui restent sont premiers.
À retenir : il y a 25 nombres premiers inférieurs à 100. Mais il y en a une infinité au total.
On peut programmer le crible d'Ératosthène en Python : on part d'une liste de booléens, puis, pour chaque nombre $d$ encore premier avec $d \times d \leqslant n$, on barre ses multiples à partir de $d^2$.
def crible(n):
est_premier = [True] * (n + 1)
est_premier[0] = False
est_premier[1] = False
d = 2
while d * d <= n:
if est_premier[d]:
for m in range(d * d, n + 1, d):
est_premier[m] = False
d += 1
return [k for k in range(n + 1) if est_premier[k]]
Par exemple, crible(30) renvoie [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].
Dans un jeu vidéo de stratégie, vous devez classer des cristaux d'énergie selon leur pureté. Les cristaux portant des nombres premiers donnent de l'énergie…
Dans un jeu vidéo de stratégie, vous devez classer des cristaux d'énergie selon leur pureté. Les cristaux portant des nombres premiers donnent de l'énergie supplémentaire, tandis que les nombres composés doivent être traités.
Classer les nombres suivants dans le tableau de votre cahier :
$11, 15, 23, 27, 31, 39, 42, 47, 51$
Le crible d'Ératosthène est une méthode ancienne pour trouver les nombres premiers en barrant les multiples des nombres précédents. Observer le graphique suivant des…
Le crible d'Ératosthène est une méthode ancienne pour trouver les nombres premiers en barrant les multiples des nombres précédents. Observer le graphique suivant des nombres de $1$ à $20$ :
Recopier la grille dans votre cahier et compléter le processus jusqu'au nombre $50$ afin d'identifier tous les nombres premiers inférieurs à $50$.
On appelle nombres premiers jumeaux les couples de nombres premiers qui ne sont séparés que par un nombre pair (c'est-à-dire dont la différence est $2$). Par exemple,…
On appelle nombres premiers jumeaux les couples de nombres premiers qui ne sont séparés que par un nombre pair (c'est-à-dire dont la différence est $2$). Par exemple, $3$ et $5$ sont des nombres premiers jumeaux.
- a) Trouver tous les couples de nombres premiers jumeaux inférieurs à $60$.
- b) Le couple $(21, 23)$ est-il un couple de nombres premiers jumeaux ? Justifier la réponse.
Il y a une infinité de nombres premiers
Les critères de divisibilité
Pour savoir si un nombre est divisible par un autre sans poser la division, on utilise des critères.
Pour ranger les étagères d'un CDI, le documentaliste utilise les critères de divisibilité. Sans poser de division, indiquer lesquels des nombres suivants sont divisibles…
Pour ranger les étagères d'un CDI, le documentaliste utilise les critères de divisibilité. Sans poser de division, indiquer lesquels des nombres suivants sont divisibles par $3$ et lesquels le sont par $5$ :
- a) $123$
- b) $405$
- c) $1\,020$
- d) $715$
Dans un jeu de stratégie en ligne, pour déverrouiller un coffre, il faut saisir une clé à quatre chiffres de la forme $52X4$. Si le système indique que la clé est un…
Dans un jeu de stratégie en ligne, pour déverrouiller un coffre, il faut saisir une clé à quatre chiffres de la forme $52X4$. Si le système indique que la clé est un nombre divisible à la fois par $3$ et par $4$, quelles sont toutes les valeurs possibles du chiffre $X$ ? Justifier la réponse en appliquant les critères de divisibilité correspondants.
Savoir si un nombre est premier
Pour savoir si un nombre $N$ est premier, on cherche un diviseur autre que $1$ et $N$. On teste les nombres premiers dans l'ordre : $2$, $3$, $5$, $7$, $11$… avec les critères de divisibilité, et la liste des premiers inférieurs à $100$. Dès qu'on en trouve un qui divise $N$, on peut conclure : $N$ est composé.
Mais quand s'arrêter pour conclure qu'il est premier ? Si $N$ est composé, il a un diviseur premier $p$ tel que $p \leqslant \sqrt{N}$ : il suffit donc de tester les nombres premiers inférieurs ou égaux à $\sqrt{N}$. On peut programmer ce test :
def est_premier(n):
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
Retour au début. Pour $143$ : il est impair, ne finit pas par $5$, $1 + 4 + 3 = 8$ n'est pas divisible par $3$. On teste $7$ : non ($7 \times 20 = 140$). On teste $11$ : $11 \times 13 = 143$. Donc $143$ est composé : on peut ranger les croissants en $11$ piles de $13$ (ou $13$ piles de $11$).
Une application de messagerie utilise un filtre de sécurité qui ne laisse passer que les messages dont l'identifiant est un nombre premier. Classer les identifiants…
Une application de messagerie utilise un filtre de sécurité qui ne laisse passer que les messages dont l'identifiant est un nombre premier. Classer les identifiants suivants en nombres premiers ou nombres composés, en justifiant chaque décision par la recherche d'un diviseur différent de 1 et du nombre lui-même :
- a) $119$
- b) $131$
- c) $143$
- d) $151$
- e) $203$
Marc affirme en cours de mathématiques : « Le nombre $91$ est premier parce que j'ai vérifié qu'il n'est pas divisible par $2$ (il est impair), ni par $3$ (la somme de…
Marc affirme en cours de mathématiques : « Le nombre $91$ est premier parce que j'ai vérifié qu'il n'est pas divisible par $2$ (il est impair), ni par $3$ (la somme de ses chiffres est $10$), ni par $5$ (il ne se termine ni par $0$ ni par $5$). Comme j'ai déjà essayé avec les premiers nombres premiers, il n'est pas nécessaire de continuer. »\na) Expliquer quel est le critère qui indique jusqu'à quel nombre premier il faut tester les divisions pour savoir avec certitude si un nombre $N$ est premier.\nb) Jusqu'à quel nombre premier Marc aurait-il dû tester pour le nombre $91$ ?\nc) Repérer l'erreur de Marc, expliquer pourquoi son raisonnement est faux et déterminer si $91$ est premier ou composé en justifiant la réponse par une division.
Un expert en cybersécurité conçoit un système de chiffrement pour une application de messagerie. La clé de sécurité principale est un nombre $N$ obtenu en multipliant un…
Un expert en cybersécurité conçoit un système de chiffrement pour une application de messagerie. La clé de sécurité principale est un nombre $N$ obtenu en multipliant un couple de nombres premiers jumeaux compris entre $100$ et $110$. Cependant, en vérifiant la liste, il s'aperçoit que dans cet intervalle il y a deux couples de nombres premiers jumeaux, donc le choix n'est pas unique. Pour résoudre le problème, il décide que la clé sera le produit des deux nombres premiers les plus proches de $105$ (l'un en dessous et l'autre au-dessus).
Déterminer ces deux nombres premiers, vérifier en justifiant qu'ils sont bien premiers grâce à la méthode de la racine carrée, puis calculer la valeur de la clé de sécurité $N$.
Décomposition en produit de facteurs premiers
Méthode des divisions successives : on écrit le nombre à gauche d'une barre verticale. À droite, on place le plus petit nombre premier qui le divise, et on écrit le quotient en dessous. On recommence jusqu'à obtenir $1$.
On peut aussi présenter la décomposition sous forme d'arbre de facteurs : on écrit le nombre en haut, puis on le sépare en deux facteurs (pas forcément premiers) placés sur deux branches. On recommence avec chaque facteur composé, jusqu'à ce que toutes les « feuilles » soient des nombres premiers. Quel que soit le premier découpage choisi, on obtient les mêmes feuilles (unicité de la décomposition).
La décomposition donne tous les diviseurs : ce sont les produits de ses facteurs.
La décomposition sert aussi à simplifier une fraction : $\dfrac{140}{135} = \dfrac{2^2 \times 5 \times 7}{3^3 \times 5} = \dfrac{28}{27}$.
En cours de mathématiques, nous apprenons à décomposer les nombres en leurs éléments fondamentaux : les facteurs premiers. Décomposer en produit de facteurs premiers (à…
En cours de mathématiques, nous apprenons à décomposer les nombres en leurs éléments fondamentaux : les facteurs premiers. Décomposer en produit de facteurs premiers (à l'aide de la « barre verticale ») les nombres suivants :
- a) $24$
- b) $60$
- c) $100$
Un programmeur crée une liste de tous les diviseurs du nombre $30$ pour un algorithme de sécurité. Utiliser sa décomposition en facteurs premiers pour trouver tous ses…
Un programmeur crée une liste de tous les diviseurs du nombre $30$ pour un algorithme de sécurité.
Utiliser sa décomposition en facteurs premiers pour trouver tous ses diviseurs entiers naturels.
Observer l'arbre de facteurs incomplet suivant qui représente la décomposition d'un nombre entier naturel. Votre tâche est de le compléter, puis d'écrire la…
Observer l'arbre de facteurs incomplet suivant qui représente la décomposition d'un nombre entier naturel. Votre tâche est de le compléter, puis d'écrire la décomposition en produit de facteurs premiers de ce nombre à l'aide de puissances de facteurs premiers.
Diviseurs communs, PGCD et PPCM
Le PGCD fait partie du programme de cette classe (voir aussi l'algorithme d'Euclide) ; le PPCM est un simple rappel. Ils servent à résoudre des problèmes de partage et de rencontre.
Avec les décompositions : le PGCD est le produit des facteurs premiers communs, pris avec le plus petit exposant ; le PPCM est le produit de tous les facteurs premiers, pris avec le plus grand exposant.
Relation utile : $\text{PGCD}(a ; b) \times \text{PPCM}(a ; b) = a \times b$. Deux nombres dont le PGCD est $1$ sont dits premiers entre eux.
Une confiserie veut emballer $20$ sucettes à la fraise et $28$ au citron dans des sachets identiques, de façon que chacun contienne le plus grand nombre possible de…
Une confiserie veut emballer $20$ sucettes à la fraise et $28$ au citron dans des sachets identiques, de façon que chacun contienne le plus grand nombre possible de sucettes, sans les mélanger. Pour cela, elle doit calculer le PGCD.
Sur la figure, chaque division des barres représente une sucette.
Calculer le PGCD de $20$ et $28$ et expliquer combien de sucettes il y aura dans chaque sachet.
Une banque alimentaire a reçu un don de $120$ boîtes de légumes secs, $150$ litres de lait et $72$ boîtes de conserve. Elle veut préparer le plus grand nombre possible…
Une banque alimentaire a reçu un don de $120$ boîtes de légumes secs, $150$ litres de lait et $72$ boîtes de conserve. Elle veut préparer le plus grand nombre possible de colis identiques à distribuer à des familles dans le besoin, sans qu'il reste aucun produit.
- a) Combien de colis peut-elle préparer au maximum ?
- b) Quelle quantité de chaque produit contiendra chacun de ces colis ?
On sait que le PGCD de deux nombres $a$ et $b$ est $\text{PGCD}(a ; b) = 15$ et que leur produit est $a \cdot b = 6750$. Utiliser la relation mathématique entre le…
On sait que le PGCD de deux nombres $a$ et $b$ est $\text{PGCD}(a ; b) = 15$ et que leur produit est $a \cdot b = 6750$. Utiliser la relation mathématique entre le produit de deux nombres et leurs diviseurs/multiples communs pour déterminer le PPCM de ces nombres sans avoir à les calculer séparément.
Combien de diviseurs ?
Pourquoi ? Un diviseur s'obtient en choisissant, pour chaque nombre premier, un exposant entre $0$ et son exposant dans $N$ : cela fait $a+1$ choix pour $p$, $b+1$ pour $q$, etc.
Avant de faire le moindre calcul par écrit, concentrez-vous sur le nombre $72$ :\na) Estimer : pensez-vous que $72$ aura plus ou moins de $8$ diviseurs ? Écrire au moins…
Avant de faire le moindre calcul par écrit, concentrez-vous sur le nombre $72$ :\na) Estimer : pensez-vous que $72$ aura plus ou moins de $8$ diviseurs ? Écrire au moins quatre diviseurs qui vous viennent immédiatement à l'esprit pour justifier votre estimation initiale.\nb) Calculer : effectuer la décomposition de $72$ en produit de facteurs premiers et appliquer la formule du nombre de diviseurs, $(a+1)(b+1)\dots$, pour trouver le nombre exact.\nc) Vérifier : comparer la valeur obtenue avec votre estimation et rédiger une brève conclusion expliquant si votre intuition initiale était juste et pourquoi un nombre inférieur à $100$ peut avoir autant de diviseurs.
Dans une commune du département de la Creuse, la liste électorale d'un bureau de vote annexe compte exactement $105$ électeurs convoqués pour des élections locales. Le…
Dans une commune du département de la Creuse, la liste électorale d'un bureau de vote annexe compte exactement $105$ électeurs convoqués pour des élections locales. Le coordinateur doit répartir les électeurs en groupes ou en créneaux horaires comptant exactement le même nombre de personnes, avec les conditions suivantes : dans chaque créneau, il y a plus d'un électeur et on ne fait pas un unique créneau avec tous les électeurs.\na) Décomposer $105$ en produit de facteurs premiers et utiliser la formule $(a+1)(b+1)(c+1)\dots$ pour calculer combien il a de diviseurs au total.\nb) Déduire combien de façons différentes il existe d'organiser les créneaux selon les conditions du coordinateur et écrire tous les couples possibles (nombre de créneaux, électeurs par créneau).\nc) Si, à la dernière minute, $4$ personnes de plus s'inscrivent et que la liste passe à $109$ électeurs, serait-il possible d'organiser des créneaux égaux avec les mêmes conditions ? Appliquer la méthode des nombres premiers jusqu'à $\sqrt{N}$ pour vérifier si $109$ est premier et justifier les conséquences sur l'organisation.
On dit qu'un nombre entier naturel est « spécial » s'il est le produit de trois nombres premiers distincts et inférieurs à $20$. Un exemple serait…
On dit qu'un nombre entier naturel est « spécial » s'il est le produit de trois nombres premiers distincts et inférieurs à $20$. Un exemple serait $2 \cdot 3 \cdot 5 = 30$.
Déterminer le plus grand nombre « spécial » possible et le plus petit possible. Ensuite, trouver combien de diviseurs possède chacun de ces deux nombres sans avoir à les énumérer tous, en utilisant uniquement les exposants de leur décomposition en facteurs premiers.