Ressources · Terminale · Maths expertes (option Tle)

Nombres premiers

Rappels du collège (nombres premiers jusqu’à 100, décomposition, fractions irréductibles), diviseur premier et test de primalité, crible d’Ératosthène, infinité des nombres premiers démontrée, existence et unicité de la décomposition en facteurs premiers, lemme d’Euclide, nombre et somme des diviseurs, PGCD et PPCM par les décompositions, petit théorème de Fermat.

À propos de cette page

Cinq problèmes corrigés d’arithmétique : crible et test de primalité en Python, trois balises lumineuses et leur PPCM, conditionnement de 10 500 pièces et diviseurs, plages d’entiers composés autour de n!, test de Fermat et nombre de Carmichael 561.

5 problèmes, du plus simple au plus difficile. Écris tes réponses, puis « Vérifier ».

Résoudre un problème : la méthode

Je traduis l’énoncé : des périodes qui coïncident donnent un PPCM, un partage exact donne des diviseurs, une question « premier ou pas ? » donne un test jusqu’à √n.
Je décompose chaque entier en facteurs premiers et je contrôle en remultipliant.
Je cite la propriété avec ses hypothèses : critère de la racine carrée, unicité de la décomposition, petit théorème de Fermat (p premier ne divisant pas a).
Pour un programme Python, je suis les valeurs des variables pas à pas et je relie la condition de boucle au cours.
Je réponds dans les termes de l’énoncé (une heure, un nombre de boîtes, une liste) et je vérifie sur un cas.

Problème 1 · Un crible et un test de primalité en Python★★★Moyen

On étudie deux fonctions Python. La fonction crible renvoie la liste des nombres premiers inférieurs ou égaux à un entier

n ⩾ 2

; la fonction premier teste si un entier est premier par divisions successives.

def crible(n):
  est_premier = [True] * (n + 1)
  est_premier[0] = False
  est_premier[1] = False
  p = 2
  while p * p <= n:
    if est_premier[p]:
      for k in range(p * p, n + 1, p):
        est_premier[k] = False
    p = p + 1
  return [i for i in range(n + 1) if est_premier[i]]

def premier(n):
  if n < 2:
    return False
  d = 2
  while d * d <= n:
    if n % d == 0:
      return False
    d = d + 1
  return True

1. Justifier mathématiquement la condition p * p <= n de la boucle while. Pour l’appel crible(200), dernière valeur de p pour laquelle le corps de la boucle est exécuté :
Rédaction attendue. Si un entier $m ⩽ n$ est composé, il admet un diviseur premier $p$ tel que $p^{2} ⩽ m ⩽ n$ : il est donc rayé lors du passage correspondant à ce $p$ , qui vérifie $p \times p ⩽ n$ . Prolonger la boucle ne rayerait plus aucun entier. Pour $n = 200$ : $14^{2} = 196 ⩽ 200 < 225 = 15^{2}$ , la dernière valeur est $14$ (non premier : rien n’est rayé à ce passage).
2. Justifier que la boucle intérieure peut commencer à p * p au lieu de 2 * p. Pour $p = 7$ , premier entier rayé par cette boucle :
Rédaction attendue. Un multiple $m = p \times q$ avec $2 ⩽ q < p$ admet un diviseur premier inférieur ou égal à $q$ , donc strictement inférieur à $p$ : il a déjà été rayé lors d’un passage précédent. Les seuls multiples de $p$ encore à rayer sont ceux qui sont supérieurs ou égaux à $p^{2}$ . Pour $p = 7$ : $7^{2} = 49$ .
3. Nombre d’éléments de la liste renvoyée par crible(200) :
C’est le nombre de nombres premiers inférieurs ou égaux à $200$ : $25$ entre $1$ et $100$ , puis $21$ entre $101$ et $200$ . La liste contient $46$ éléments, le dernier étant $199$ .
4. Nombre de divisions (calculs de n % d) effectuées par l’appel premier(1999) :
$44^{2} = 1 936 ⩽ 1 999 < 2 025 = 45^{2}$ : la boucle teste $d = 2, 3, \dots, 44$ , soit $43$ divisions. Aucune n’a un reste nul (par exemple $7 \times 285 = 1 995$ , $13 \times 153 = 1 989$ , $43 \times 46 = 1 978$ ) : la fonction renvoie True, $1 999$ est premier.
5. Pour l’appel premier(2809), valeur de d au moment où la fonction renvoie False :
$2 809 = 53^{2}$ et $53$ est premier : le plus petit diviseur de $2 809$ supérieur ou égal à $2$ est $53$ . La fonction échoue de $d = 2$ à $d = 52$ , puis renvoie False pour $d = 53$ . Pour un entier composé, c’est le cas le plus coûteux : son plus petit diviseur premier est exactement $\sqrt{n}$ .

Problème 2 · Trois balises lumineuses★★★Moyen

À l’entrée d’un port, trois balises s’allument à intervalles réguliers : la première toutes les

154

secondes, la deuxième toutes les

220

secondes, la troisième toutes les

308

secondes. À 20 h 00 min 00 s, les trois balises s’allument en même temps.

1. Décomposer $154$ , $220$ et $308$ en produits de facteurs premiers. Plus grand facteur premier commun aux trois :
$154 = 2 \times 7 \times 11$ ; $220 = 2^{2} \times 5 \times 11$ ; $308 = 2^{2} \times 7 \times 11$ . Les facteurs communs aux trois sont $2$ et $11$ : le plus grand est $11$ .
2. Durée, en secondes, entre deux allumages simultanés :
C’est le PPCM des trois périodes : chaque facteur premier avec son exposant maximal, $2^{2} \times 5 \times 7 \times 11$ , soit $1 540$ secondes.
3. Cette durée vaut min s.
$1 540 = 25 \times 60 + 40$ : $25$ minutes et $40$ secondes. Le deuxième allumage simultané a lieu à 20 h 25 min 40 s.
4. PGCD des trois périodes, en secondes :
Facteurs communs avec l’exposant minimal : $2^{1}$ (à cause de $154$ ) et $11$ . $pgcd = 22$ secondes : c’est la plus grande durée dont les trois périodes sont des multiples ; en regardant le port toutes les $22$ secondes à partir de 20 h, on ne manque aucun allumage.
5. Nombre d’allumages simultanés entre 20 h 00 et minuit, bornes comprises :
De 20 h à minuit, il s’écoule $4 \times 3 600 = 14 400$ secondes. Les allumages simultanés ont lieu aux instants $1 540 k$ avec $1 540 k ⩽ 14 400$ ; or $1 540 \times 9 = 13 860$ $⩽ 14 400 < 15 400$ $= 1 540 \times 10$ , donc $k \in {0; 1; \dots; 9}$ : $10$ allumages, le dernier à 23 h 51 min 00 s.
6. Un élève affirme que les trois balises s’allument ensemble toutes les $154 \times 220 \times 308$ secondes. Expliquer son erreur. Quotient de ce produit par la durée trouvée plus haut :
Rédaction attendue. $154 \times 220 \times 308 = 10 435 040$ est bien un multiple commun des trois périodes, mais pas le plus petit : les facteurs $2$ et $11$ , communs aux trois, y sont comptés plusieurs fois. $10 435 040 = 1 540 \times 6 776$ . L’élève confond « un multiple commun » et « le plus petit multiple commun ».

Problème 3 · Conditionner 10 500 pièces★★★Difficile

Un atelier doit répartir un lot de

10 500

pièces identiques dans des boîtes contenant toutes le même nombre de pièces, sans qu’il en reste. Un conditionnement est un couple (nombre de boîtes ; contenu d’une boîte).

1. Décomposer $10 500$ en produit de facteurs premiers. Exposant de $5$ :
$10 500 = 105 \times 100$ , avec $105 = 3 \times 5 \times 7$ et $100 = 2^{2} \times 5^{2}$ , donc $10 500 = 2^{2} \times 3 \times 5^{3} \times 7$ .
2. Nombre de conditionnements possibles :
Un conditionnement correspond à un diviseur positif $m$ de $10 500$ (le contenu d’une boîte), le nombre de boîtes valant $10 500 \div m$ . Le nombre de diviseurs est $(2 + 1) (1 + 1) (3 + 1) (1 + 1)$ $= 3 \times 2 \times 4 \times 2 = 48$ .
3. Nombre de contenus possibles qui sont des carrés parfaits :
Un diviseur $2^{b_{1}} \times 3^{b_{2}} \times 5^{b_{3}} \times 7^{b_{4}}$ est un carré parfait si et seulement si tous ses exposants sont pairs : $b_{1} \in {0; 2}$ , $b_{2} = 0$ , $b_{3} \in {0; 2}$ , $b_{4} = 0$ . Cela fait $2 \times 2 = 4$ contenus : $1$ , $4$ , $25$ et $100$ .
4. Somme de tous les diviseurs positifs de $10 500$ :
$σ (10 500) = (1 + 2 + 4) (1 + 3)$ $\times (1 + 5 + 25 + 125) (1 + 7)$ $= 7 \times 4 \times 156 \times 8$ . Or $7 \times 4 = 28$ , $28 \times 156 = 4 368$ et $4 368 \times 8 = 34 944$ .
5. Démontrer que le produit de tous les diviseurs positifs de $10 500$ est égal à $10 500^{k}$ . Valeur de $k$ :
Rédaction attendue. Notons $N = 10 500$ , $D$ l’ensemble de ses $48$ diviseurs positifs et $P$ leur produit. Quand $d$ parcourt $D$ , $N / d$ parcourt aussi $D$ (chaque diviseur est atteint une fois) : le produit des $N / d$ vaut donc aussi $P$ . En multipliant membre à membre les $48$ égalités $d \times \frac{N}{d} = N$ , on obtient $P \times P = N^{48}$ , et, $P$ étant positif, $P = N^{24}$ .
6. L’atelier impose un contenu compris entre $100$ et $200$ pièces par boîte. Nombre de conditionnements possibles :
Diviseurs de $2^{2} \times 3 \times 5^{3} \times 7$ entre $100$ et $200$ : $100 = 2^{2} \times 5^{2}$ , $105 = 3 \times 5 \times 7$ , $125 = 5^{3}$ , $140 = 2^{2} \times 5 \times 7$ , $150 = 2 \times 5^{2} \times 3$ et $175 = 5^{2} \times 7$ . Les autres entiers de cet intervalle demanderaient $2^{3}$ , $3^{2}$ , $7^{2}$ ou un autre nombre premier. D’où $6$ conditionnements : $105$ boîtes de $100$ , $100$ boîtes de $105$ , $84$ de $125$ , $75$ de $140$ , $70$ de $150$ et $60$ de $175$ .

Problème 4 · De longues plages sans nombre premier★★★Difficile

Pour un entier

n ⩾ 1

, on note

n! = 1 \times 2 \times \dots \times n

(factorielle

n

). On donne

6! = 720

1. Montrer que $727$ est premier. Plus grand nombre premier qu’il faut tester :
$26^{2} = 676 ⩽ 727 < 729 = 27^{2}$ : on teste les nombres premiers jusqu’à $26$ , le plus grand étant $23$ . $727$ est impair ; $7 + 2 + 7 = 16$ ; ni $0$ ni $5$ ; $7 \times 103 = 721$ (reste $6$ ), $11 \times 66 = 726$ (reste $1$ ), $13 \times 55 = 715$ (reste $12$ ), $17 \times 42 = 714$ (reste $13$ ), $19 \times 38 = 722$ (reste $5$ ), $23 \times 31 = 713$ (reste $14$ ). Aucun reste nul : $727$ est premier.
2. Les entiers de $722$ à $726$ s’écrivent $720 + k$ avec $2 ⩽ k ⩽ 6$ . Justifier qu’ils sont tous composés. Plus grand facteur premier de $723$ :
Rédaction attendue. $720 = 6!$ est divisible par $2$ , $3$ , $4$ , $5$ et $6$ ; donc $720 + k$ est divisible par $k$ , avec $1 < k < 720 + k$ : il est composé. Décompositions : $722 = 2 \times 19^{2}$ , $723 = 3 \times 241$ , $724 = 2^{2} \times 181$ , $725 = 5^{2} \times 29$ , $726 = 6 \times 11^{2} = 2 \times 3 \times 11^{2}$ .
3. Soit $n ⩾ 2$ . Démontrer que les $n$ entiers consécutifs $(n + 1)! + 2$ , $(n + 1)! + 3$ , …, $(n + 1)! + (n + 1)$ sont tous composés. Pour $n = 3$ , plus petit de ces entiers :
Rédaction attendue. Soit $k$ un entier tel que $2 ⩽ k ⩽ n + 1$ . $k$ est l’un des facteurs de $(n + 1)! = 1 \times 2 \times \dots \times (n + 1)$ , donc $k$ divise $(n + 1)!$ , et $k$ divise $(n + 1)! + k$ . Comme $1 < k < (n + 1)! + k$ , l’entier $(n + 1)! + k$ est composé. Pour $n = 3$ : $4! = 24$ , et les entiers $26 = 2 \times 13$ , $27 = 3^{3}$ et $28 = 2^{2} \times 7$ sont composés ; le plus petit est $26$ . Pour $n = 5$ , on retrouve les entiers de $722$ à $726$ de la question précédente.
4. En déduire l’existence de $100$ entiers consécutifs tous composés. Le premier d’entre eux s’écrit $m! + 2$ : valeur de $m$ :
On applique la question précédente avec $n = 100$ , donc $m = n + 1 = 101$ : les $100$ entiers consécutifs $101! + 2$ , $101! + 3$ , …, $101! + 101$ sont tous composés. L’argument vaut pour toute longueur : l’écart entre deux nombres premiers consécutifs peut être aussi grand que l’on veut.
5. Expliquer pourquoi ce résultat ne contredit pas le théorème d’Euclide. Nombre de nombres premiers entre $401$ et $500$ (cours) :
Rédaction attendue. Le théorème d’Euclide affirme qu’au-delà de tout entier il existe encore un nombre premier ; il ne dit rien de leur répartition. Les nombres premiers sont en nombre infini mais de plus en plus espacés en moyenne, comme le montrent les effectifs par tranche de $100$ ( $25$ , $21$ , $16$ , $16$ , puis $17$ entre $401$ et $500$ ) : rien n’interdit des plages arbitrairement longues sans nombre premier entre deux d’entre eux.

Problème 5 · Le test de Fermat et le nombre 561★★★Difficile

Pour un entier

n ⩾ 2

et un entier

a

, on dit que

n

passe le test de Fermat en base $a$ lorsque

a^{n - 1} \equiv 1 [n]

. D’après le petit théorème de Fermat, un nombre premier

n

passe le test pour tout entier

a

non divisible par

n

. On étudie

n = 561

1. Décomposer $561$ en facteurs premiers. Plus grand facteur premier :
$5 + 6 + 1 = 12$ : $561 = 3 \times 187$ , et $187 = 11 \times 17$ . Donc $561 = 3 \times 11 \times 17$ n’est pas premier.
2. Soit $a$ un entier premier avec $561$ . Démontrer que $a^{2} \equiv 1 [3]$ , $a^{10} \equiv 1 [11]$ et $a^{16} \equiv 1 [17]$ . Quotient de $560$ par $16$ :
Rédaction attendue. $a$ est premier avec $561$ , donc aucun des nombres premiers $3$ , $11$ , $17$ ne divise $a$ . Le petit théorème de Fermat donne $a^{3 - 1} = a^{2} \equiv 1 [3]$ , $a^{10} \equiv 1 [11]$ et $a^{16} \equiv 1 [17]$ . Enfin $560 = 16 \times 35$ .
3. En déduire que $a^{560} \equiv 1$ modulo $3$ , $11$ et $17$ , puis que $561$ divise $a^{560} - 1$ . Reste de la division de $2^{560}$ par $561$ :
Rédaction attendue. $560 = 2 \times 280 = 10 \times 56 = 16 \times 35$ , donc $a^{560} = (a^{2})^{280} \equiv 1 [3]$ , $a^{560} = (a^{10})^{56} \equiv 1 [11]$ et $a^{560} = (a^{16})^{35} \equiv 1 [17]$ . Les nombres premiers distincts $3$ , $11$ et $17$ divisent $a^{560} - 1$ ; si cet entier est non nul, ils figurent dans sa décomposition, donc leur produit $561$ le divise ; s’il est nul, c’est évident. Avec $a = 2$ , premier avec $561$ : $2^{560} \equiv 1 [561]$ , le reste est $1$ , alors que $561$ n’est pas premier.
4. Justifier que $3^{560} ≢ 1 [561]$ . Reste de la division de $3^{560} - 1$ par $3$ :
Rédaction attendue. $3^{560} - 1 = 3 \times 3^{559} - 3 + 2$ : son reste dans la division par $3$ est $2$ , donc $3$ ne divise pas $3^{560} - 1$ . Si $561$ divisait $3^{560} - 1$ , son diviseur $3$ le diviserait aussi : contradiction. Donc $3^{560} ≢ 1 [561]$ ; ici, l’échec vient de ce que $3$ divise $561$ .
5. Seule base $a$ comprise entre $2$ et $4$ pour laquelle $561$ échoue au test de Fermat :
$2$ et $4$ sont premiers avec $561$ (impair, et sans facteur commun avec $4$ ) : d’après la question 3, $561$ passe le test en bases $2$ et $4$ . Il échoue en base $3$ (question 4). Un entier composé qui passe le test en toute base première avec lui est appelé nombre de Carmichael ; $561$ est le plus petit d’entre eux. Le test de Fermat seul ne prouve donc jamais qu’un entier est premier.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs