Ressources · Terminale · Maths expertes (option Tle)

Nombres premiers

Q: Comment savoir si un entier est premier ?

On encadre l’entier n entre deux carrés consécutifs, puis on teste sa divisibilité par les seuls nombres premiers p tels que p² ≤ n. Pour 223 : 14² = 196 ≤ 223 < 225 = 15², on teste 2, 3, 5, 7, 11 et 13 ; aucun ne divise 223, donc 223 est premier. Inutile d’aller plus loin : un entier composé a toujours un diviseur premier inférieur ou égal à sa racine carrée.

Q: Pourquoi 1 n’est-il pas un nombre premier ?

Un nombre premier a exactement deux diviseurs positifs, 1 et lui-même ; 1 n’en a qu’un seul. Ce choix garantit l’unicité de la décomposition en facteurs premiers : si 1 était premier, on pourrait écrire 6 = 2 × 3, mais aussi 6 = 1 × 2 × 3 ou 6 = 1 × 1 × 2 × 3, sans fin.

Q: Comment démontrer qu’il existe une infinité de nombres premiers ?

Par l’absurde : si p₁, …, pᵣ étaient tous les nombres premiers, l’entier N = p₁ × … × pᵣ + 1 aurait un diviseur premier p, forcément dans la liste. Alors p diviserait le produit et N, donc leur différence 1 : impossible. C’est une démonstration exigible au programme de maths expertes.

Q: Comment trouver le nombre de diviseurs d’un entier ?

On décompose l’entier en facteurs premiers, puis on multiplie les exposants augmentés de 1. Pour 1 225 = 5² × 7², on obtient (2 + 1)(2 + 1) = 9 diviseurs : un nombre impair, ce qui est normal, car 1 225 = 35² est un carré parfait.

Q: Que dit le petit théorème de Fermat ?

Si p est un nombre premier qui ne divise pas l’entier a, alors a^(p − 1) ≡ 1 [p] ; et pour tout entier a, a^p ≡ a [p]. Il sert à trouver le reste d’une grande puissance : 10¹⁸ ≡ 1 [19], donc 10⁴⁰ = (10¹⁸)² × 10⁴ ≡ 10 000 [19], et comme 10 000 = 526 × 19 + 6, le reste de 10⁴⁰ modulo 19 est 6.

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

Ce cours de maths expertes de Terminale commence par les rappels du collège (nombres premiers jusqu’à 100, décomposition de 3 150, fraction irréductible), puis démontre l’existence d’un diviseur premier, le test par la racine carrée et le crible d’Ératosthène. Il rédige la démonstration exigible de l’infinité des nombres premiers, établit la décomposition en facteurs premiers avec le lemme d’Euclide, le nombre et la somme des diviseurs, le PGCD et le PPCM par les exposants, et se termine par le petit théorème de Fermat démontré.

Rappels du collège : nombres premiers et décomposition

Ce qu’il faut savoir

Définition. Un entier naturel $p$ est premier lorsqu’il admet exactement deux diviseurs positifs : $1$ et $p$ . En particulier $p ⩾ 2$ . Un entier $n ⩾ 2$ qui n’est pas premier est dit composé : il s’écrit $n = a b$ avec $2 ⩽ a ⩽ b < n$ .

Cas particuliers. $0$ et $1$ ne sont ni premiers ni composés : $1$ n’a qu’un diviseur positif, et tout entier non nul divise $0$ . $2$ est le seul nombre premier pair : tout autre entier pair admet $2$ comme diviseur.

Les $25$ nombres premiers inférieurs à $100$ (à connaître) : $2$ , $3$ , $5$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ , $31$ , $37$ , $41$ , $43$ , $47$ , $53$ , $59$ , $61$ , $67$ , $71$ , $73$ , $79$ , $83$ , $89$ , $97$ .

Critères de divisibilité (collège). Un entier est divisible par $2$ si son chiffre des unités est pair ; par $3$ (resp. $9$ ) si la somme de ses chiffres est divisible par $3$ (resp. $9$ ) ; par $5$ si son chiffre des unités est $0$ ou $5$ . Pour $7$ , $11$ , $13$ …, on effectue la division.

Décomposer en facteurs premiers. On divise par le plus petit nombre premier possible ( $2$ , puis $3$ , $5$ , $7$ …), on recommence avec le quotient, et on s’arrête quand le quotient vaut $1$ . On écrit le produit avec des puissances, facteurs dans l’ordre croissant.

Fraction irréductible. On décompose le numérateur et le dénominateur, puis on simplifie par tous les facteurs premiers communs.

Exemples

Premier ou composé ? $253$ est impair, $2 + 5 + 3 = 10$ n’est pas divisible par $3$ , il ne se termine ni par $0$ ni par $5$ , et $7 \times 36 = 252$ (reste $1$ ). Mais $253 = 11 \times 23$ : $253$ est composé, bien qu’aucun critère du collège ne le révèle.

Décomposition rédigée de $3 150$ . $3 150 = 2 \times 1 575$ ; $1 + 5 + 7 + 5 = 18$ , donc $1 575 = 3 \times 525 = 3^{2} \times 175$ ; enfin $175 = 5 \times 35 = 5^{2} \times 7$ . D’où $3 150 = 2 \times 3^{2} \times 5^{2} \times 7 .$ Contrôle : $2 \times 9 \times 25 \times 7 = 3 150$ .

Fraction irréductible. $4 620 = 2^{2} \times 3 \times 5 \times 7 \times 11$ . Les facteurs premiers communs avec $3 150$ sont $2$ , $3$ , $5$ et $7$ , chacun avec l’exposant $1$ : $2 \times 3 \times 5 \times 7 = 210$ . Donc $\frac{3 150}{4 620} = \frac{210 \times 15}{210 \times 22} = \frac{15}{22}$ , irréductible car $15 = 3 \times 5$ et $22 = 2 \times 11$ n’ont aucun facteur premier commun.

Réflexe — Pour décomposer, je teste les nombres premiers dans l’ordre croissant, je garde le même tant qu’il divise le quotient, et je contrôle en remultipliant les facteurs.

Attention — $3 150 = 2 \times 9 \times 175$ est une égalité juste, mais ce n’est pas une décomposition en facteurs premiers : $9$ et $175$ ne sont pas premiers. Et un entier impair n’est pas forcément premier : $253 = 11 \times 23$ .

1 / 6

Diviseur premier, test de primalité et crible d’Ératosthène

Ce qu’il faut savoir

Existence d’un diviseur premier. Tout entier $n ⩾ 2$ admet au moins un diviseur premier : son plus petit diviseur supérieur ou égal à $2$ est un nombre premier.

Test de primalité. Si un entier $n ⩾ 2$ est composé, il admet un diviseur premier $p$ tel que $p^{2} ⩽ n$ . Par contraposée : si aucun nombre premier $p$ vérifiant $p^{2} ⩽ n$ ne divise $n$ , alors $n$ est premier.

Méthode. J’encadre $n$ entre deux carrés consécutifs, $k^{2} ⩽ n < (k + 1)^{2}$ , puis je teste la divisibilité de $n$ par les nombres premiers inférieurs ou égaux à $k$ . Si aucun ne divise $n$ , $n$ est premier.

Crible d’Ératosthène (liste des nombres premiers jusqu’à $N$ ). On écrit les entiers de $2$ à $N$ . Tant que $p^{2} ⩽ N$ , on garde le plus petit entier $p$ non encore traité et non rayé, et on raye ses multiples à partir de $p^{2}$ . Les entiers non rayés sont exactement les nombres premiers inférieurs ou égaux à $N$ . La méthode est attribuée à Ératosthène de Cyrène, savant grec du III^e siècle av. J.-C., par Nicomaque de Gérase.

Répartition. Les nombres premiers se raréfient, sans disparaître :

Tranche	$1$ à $100$	$101$ à $200$	$201$ à $300$	$301$ à $400$	$401$ à $500$
Nombres premiers	$25$	$21$	$16$	$16$	$17$

Exemples

Démonstration de l’existence d’un diviseur premier. L’ensemble des diviseurs de $n$ supérieurs ou égaux à $2$ est une partie non vide de $ℕ$ (il contient $n$ ) : il admet un plus petit élément $d$ . Si $d$ n’était pas premier, il aurait un diviseur $d'$ tel que $2 ⩽ d' < d$ ; comme $d'$ divise $d$ et $d$ divise $n$ , $d'$ diviserait $n$ , ce qui contredit le choix de $d$ . Donc $d$ est premier. $∎$

Démonstration du test. Si $n$ est composé, $n = a b$ avec $2 ⩽ a ⩽ b$ , donc $a^{2} ⩽ a b = n$ . Le plus petit diviseur premier $p$ de $a$ vérifie $p ⩽ a$ , donc $p^{2} ⩽ n$ ; et $p$ divise $a$ , qui divise $n$ , donc $p$ divise $n$ . $∎$

Réponse rédigée : $331$ est-il premier ? $18^{2} = 324 ⩽ 331 < 361 = 19^{2}$ : on teste $2$ , $3$ , $5$ , $7$ , $11$ , $13$ et $17$ . $331$ est impair ; $3 + 3 + 1 = 7$ n’est pas divisible par $3$ ; il ne se termine ni par $0$ ni par $5$ ; $7 \times 47 = 329$ (reste $2$ ) ; $11 \times 30 = 330$ (reste $1$ ) ; $13 \times 25 = 325$ (reste $6$ ) ; $17 \times 19 = 323$ (reste $8$ ). Aucun reste nul : $331$ est premier.

Aller jusqu’au bout. Pour $437$ : $20^{2} = 400 ⩽ 437 < 441 = 21^{2}$ , on teste jusqu’à $19$ . Les essais de $2$ à $17$ échouent, mais $437 = 19 \times 23$ : $437$ est composé. Le dernier nombre testé peut être le bon.

Crible jusqu’à $120$ . $11^{2} = 121 > 120$ : il suffit de rayer les multiples de $2$ , $3$ , $5$ et $7$ . Il reste les $30$ nombres premiers inférieurs ou égaux à $120$ ; les cinq plus grands sont $101$ , $103$ , $107$ , $109$ et $113$ .

Réflexe — J’encadre $n$ entre deux carrés consécutifs, je ne teste que des nombres premiers, et je vais jusqu’à la racine carrée, ni plus loin, ni moins loin.

Attention — S’arrêter trop tôt fait déclarer premier un entier composé ( $437$ ). Le chiffre des unités ne prouve rien : un nombre premier supérieur à $10$ se termine par $1$ , $3$ , $7$ ou $9$ , mais $119 = 7 \times 17$ se termine par $9$ sans être premier.

2 / 6

L’infinité des nombres premiers

Ce qu’il faut savoir

Théorème. L’ensemble des nombres premiers est infini. C’est une démonstration exigible du programme (ci-dessous).

L’idée. À partir d’une liste finie de nombres premiers $p_{1}, p_{2}, \dots, p_{r}$ , l’entier $N = p_{1} \times p_{2} \times \dots \times p_{r} + 1$ n’est divisible par aucun des $p_{i}$ (le reste de la division vaut $1$ ). Or $N$ admet un diviseur premier : c’est un nombre premier qui n’est pas dans la liste.

Un peu d’histoire. Le résultat figure dans les Éléments d’Euclide (livre IX, proposition 20), sous la forme : les nombres premiers sont plus nombreux que toute multitude de nombres premiers proposée. Euclide raisonne directement, comme dans l’idée ci-dessus ; la rédaction par l’absurde est aujourd’hui la plus courante.

Ce que le théorème ne dit pas. Il ne donne aucune formule produisant les nombres premiers, et il n’interdit pas de très longues plages d’entiers consécutifs tous composés (problème 4).

Exemples

Démonstration (exigible), par l’absurde. Supposons qu’il n’existe qu’un nombre fini de nombres premiers, notés $p_{1}, p_{2}, \dots, p_{r}$ . Posons $N = p_{1} \times p_{2} \times \dots \times p_{r} + 1$ . Comme $N ⩾ 2 + 1 = 3$ , $N$ admet un diviseur premier $p$ (partie 2). Par hypothèse, $p$ est l’un des $p_{i}$ : il divise donc le produit $p_{1} \times \dots \times p_{r}$ . Divisant $N$ et ce produit, $p$ divise leur différence, c’est-à-dire $1$ . C’est impossible, puisque $p ⩾ 2$ . L’ensemble des nombres premiers est donc infini. $∎$

Sur deux listes. Avec la liste ${2; 7}$ : $N = 2 \times 7 + 1 = 15 = 3 \times 5$ . $N$ n’est pas premier, mais ses facteurs premiers $3$ et $5$ sont hors de la liste. Avec la liste ${2; 3; 5}$ : $N = 31$ , qui est lui-même premier. Dans les deux cas, la construction fournit au moins un nombre premier nouveau.

Réflexe — Dans une rédaction par l’absurde, j’écris l’hypothèse (« un nombre fini de nombres premiers $p_{1}, \dots, p_{r}$ »), je construis $N$ , je cite l’existence d’un diviseur premier, puis j’aboutis à « $p$ divise $1$ ».

Attention — Il ne faut pas écrire que $N = p_{1} \times \dots \times p_{r} + 1$ « est premier » : $2 \times 7 + 1 = 15$ ne l’est pas. On affirme seulement que $N$ a un diviseur premier ; c’est l’appartenance de ce diviseur à la liste qui donne la contradiction.

3 / 6

Décomposition en facteurs premiers et diviseurs

Ce qu’il faut savoir

Théorème fondamental de l’arithmétique. Tout entier $n ⩾ 2$ s’écrit comme un produit de nombres premiers $n = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times \dots \times p_{r}^{a_{r}},$ avec $p_{1} < p_{2} < \dots < p_{r}$ premiers et des exposants $a_{i} ⩾ 1$ , et cette écriture est unique : c’est la décomposition en facteurs premiers de $n$ .

Lemme d’Euclide. Si un nombre premier $p$ divise un produit $a b$ , alors $p$ divise $a$ ou $p$ divise $b$ . Plus généralement, si $p$ divise un produit de plusieurs entiers, il divise l’un d’eux.

Diviseurs. Les diviseurs positifs de $n$ sont exactement les entiers $p_{1}^{b_{1}} \times \dots \times p_{r}^{b_{r}}$ avec $0 ⩽ b_{i} ⩽ a_{i}$ pour tout $i$ . Il y en a $(a_{1} + 1) (a_{2} + 1) \dots (a_{r} + 1)$ , et leur somme, notée $σ (n)$ , vaut $σ (n) = \prod_{i = 1}^{r} (1 + p_{i} + \dots + p_{i}^{a_{i}}) .$

Pourquoi. Un diviseur s’obtient en choisissant chaque exposant $b_{i}$ parmi les $a_{i} + 1$ valeurs $0, 1, \dots, a_{i}$ . En développant le produit qui donne $σ (n)$ , chaque diviseur apparaît une fois et une seule, grâce à l’unicité de la décomposition. Contrôle : chaque parenthèse est une somme géométrique, $1 + p + \dots + p^{a} = \frac{p^{a + 1} - 1}{p - 1}$ .

Carrés et cubes. $n$ est un carré parfait si et seulement si tous les exposants $a_{i}$ sont pairs ; c’est un cube parfait si et seulement s’ils sont tous multiples de $3$ . Conséquence : $n$ a un nombre impair de diviseurs positifs si et seulement si c’est un carré parfait (exercice 4.5).

Exemples

Démonstration du lemme d’Euclide (avec le théorème de Gauss). Supposons que $p$ ne divise pas $a$ . Les seuls diviseurs positifs de $p$ sont $1$ et $p$ , et $p$ ne divise pas $a$ , donc $pgcd (a; p) = 1$ . Comme $p$ divise $a b$ et que $p$ est premier avec $a$ , le théorème de Gauss donne : $p$ divise $b$ .

Existence de la décomposition (récurrence forte). Supposons que tout entier $m$ tel que $2 ⩽ m < n$ soit un produit de nombres premiers. Si $n$ est premier, c’est terminé. Sinon $n = a b$ avec $2 ⩽ a < n$ et $2 ⩽ b < n$ : $a$ et $b$ sont des produits de nombres premiers, donc $n$ aussi.

Unicité (idée). Si $p_{1} \times \dots \times p_{k} = q_{1} \times \dots \times q_{l}$ avec des facteurs premiers, $p_{1}$ divise le produit des $q_{j}$ , donc l’un d’eux d’après le lemme d’Euclide ; ce $q_{j}$ étant premier, $q_{j} = p_{1}$ . On simplifie par $p_{1}$ et on recommence : les deux listes de facteurs sont les mêmes.

Réponse rédigée : diviseurs de $4 312$ . $4 312 = 2 \times 2 156$ $= 2^{2} \times 1 078 = 2^{3} \times 539$ et $539 = 7 \times 77 = 7^{2} \times 11$ , donc $4 312 = 2^{3} \times 7^{2} \times 11$ . Nombre de diviseurs : $(3 + 1) (2 + 1) (1 + 1) = 24$ . Somme : $σ (4 312) = (1 + 2 + 4 + 8)$ $\times (1 + 7 + 49) (1 + 11)$ $= 15 \times 57 \times 12$ $= 10 260$ .

Liste des diviseurs de $245 = 5 \times 7^{2}$ . Ce sont les $5^{b} \times 7^{c}$ avec $b \in {0; 1}$ et $c \in {0; 1; 2}$ : $1$ , $7$ , $49$ , $5$ , $35$ et $245$ , soit $2 \times 3 = 6$ diviseurs.

Réflexe — Pour une question de diviseurs, je décompose d’abord ; je compte avec les exposants augmentés de $1$ ; je somme avec une parenthèse par facteur premier, de $p^{0} = 1$ à $p^{a}$ .

Attention — Le nombre de diviseurs de $p^{a} q^{b}$ est $(a + 1) (b + 1)$ , pas $a b$ : l’exposant $0$ compte. Et le lemme d’Euclide exige un nombre premier : $6$ divise $4 \times 9 = 36$ sans diviser ni $4$ ni $9$ .

4 / 6

PGCD et PPCM par les décompositions

Ce qu’il faut savoir

Propriété. On écrit $a$ et $b$ (entiers supérieurs ou égaux à $2$ ) sur la même liste de nombres premiers $p_{1}, \dots, p_{r}$ , avec des exposants éventuellement nuls : $a = p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ et $b = p_{1}^{b_{1}} \dots p_{r}^{b_{r}}$ . Alors $pgcd (a; b) = p_{1}^{min (a_{1}, b_{1})} \dots p_{r}^{min (a_{r}, b_{r})}$ et $ppcm (a; b) = p_{1}^{max (a_{1}, b_{1})} \dots p_{r}^{max (a_{r}, b_{r})} .$

Relation. $pgcd (a; b) \times ppcm (a; b) = a b$ , car $min (a_{i}, b_{i}) + max (a_{i}, b_{i}) = a_{i} + b_{i}$ pour chaque $i$ .

Premiers entre eux. $a$ et $b$ sont premiers entre eux si et seulement s’ils n’ont aucun facteur premier commun ; on a alors $ppcm (a; b) = a b$ .

Le PPCM, plus petit multiple commun strictement positif, n’est pas cité par le programme de maths expertes : il reste commode pour les phénomènes périodiques. Pour de grands entiers difficiles à décomposer, l’algorithme d’Euclide reste la méthode la plus rapide pour le PGCD.

Exemples

Réponse rédigée. $1 176 = 2^{3} \times 3 \times 7^{2}$ et $1 960 = 2^{3} \times 5 \times 7^{2}$ . Sur la liste $2$ , $3$ , $5$ , $7$ : $1 176 = 2^{3} \times 3^{1} \times 5^{0} \times 7^{2}$ et $1 960 = 2^{3} \times 3^{0} \times 5^{1} \times 7^{2}$ . Exposants minimaux : $pgcd (1 176; 1 960) = 2^{3} \times 7^{2} = 392$ . Exposants maximaux : $ppcm (1 176; 1 960)$ $= 2^{3} \times 3 \times 5 \times 7^{2} = 5 880$ . Contrôle : $392 \times 5 880 = 2 304 960$ et $1 176 \times 1 960 = 2 304 960$ .

Fraction irréductible. $\frac{1 176}{1 960} = \frac{392 \times 3}{392 \times 5} = \frac{3}{5}$ .

Démonstration pour le PGCD. Un diviseur positif commun à $a$ et $b$ s’écrit $p_{1}^{c_{1}} \dots p_{r}^{c_{r}}$ avec $c_{i} ⩽ a_{i}$ et $c_{i} ⩽ b_{i}$ , c’est-à-dire $c_{i} ⩽ min (a_{i}, b_{i})$ pour tout $i$ . Le plus grand s’obtient en prenant $c_{i} = min (a_{i}, b_{i})$ pour chaque $i$ . Pour les multiples communs, on raisonne de même avec $max$ .

Réflexe — J’écris les deux décompositions sur la même liste de nombres premiers (exposants nuls compris), je prends les exposants minimaux pour le PGCD, maximaux pour le PPCM, et je contrôle avec $pgcd \times ppcm = a b$ .

Attention — Le PGCD ne garde que les facteurs communs, le PPCM garde tous les facteurs. Et la relation $pgcd \times ppcm = a b$ ne vaut que pour deux entiers : pour $2$ , $2$ et $2$ , PGCD et PPCM valent $2$ , et $2 \times 2 \neq 2 \times 2 \times 2$ .

5 / 6

Petit théorème de Fermat

Ce qu’il faut savoir

Petit théorème de Fermat. Soit $p$ un nombre premier et $a$ un entier.

Si $p$ ne divise pas $a$ , alors $a^{p - 1} \equiv 1 [p]$ .
Pour tout entier $a$ , $a^{p} \equiv a [p]$ .

Reste d’une grande puissance. Si $p$ ne divise pas $a$ et si $m = (p - 1) q + r$ (division euclidienne de $m$ par $p - 1$ ), alors $a^{m} = (a^{p - 1})^{q} \times a^{r} \equiv a^{r} [p]$ .

Test de Fermat. Si un entier $a$ non divisible par $n$ vérifie $a^{n - 1} ≢ 1 [n]$ , alors $n$ n’est pas premier : on dit que $a$ est un témoin. La réciproque du théorème est fausse : un entier composé peut vérifier $a^{n - 1} \equiv 1 [n]$ (problème 5).

Un peu d’histoire. Pierre de Fermat énonce ce résultat dans une lettre à Bernard Frénicle de Bessy d’octobre 1640, sans démonstration. Leibniz en rédige une vers 1683 sans la publier ; les premières démonstrations publiées sont dues à Euler, à partir de 1741.

Exemples

Démonstration (non exigible ; le programme la propose comme problème). Étape 1. Pour $1 ⩽ k ⩽ p - 1$ , $p$ divise $(\binom{p}{k})$ . En effet $k (\binom{p}{k}) = p (\binom{p - 1}{k - 1})$ , donc $p$ divise $k (\binom{p}{k})$ ; comme $1 ⩽ k ⩽ p - 1$ , $p$ ne divise pas $k$ et $p$ est premier avec $k$ : le théorème de Gauss donne $p$ divise $(\binom{p}{k})$ .

Étape 2. Par la formule du binôme, $(a + 1)^{p} = a^{p} + \sum_{k = 1}^{p - 1} (\binom{p}{k}) a^{k} + 1$ , et chaque terme de la somme est un multiple de $p$ : $(a + 1)^{p} \equiv a^{p} + 1 [p]$ .

Étape 3. Récurrence sur $a \in ℕ$ : $0^{p} = 0$ ; si $a^{p} \equiv a [p]$ , alors $(a + 1)^{p} \equiv a^{p} + 1 \equiv a + 1 [p]$ . Pour $a$ négatif, on remplace $a$ par son reste $r$ modulo $p$ : $a^{p} \equiv r^{p} \equiv r \equiv a [p]$ .

Étape 4. Si $p$ ne divise pas $a$ : $p$ divise $a^{p} - a = a (a^{p - 1} - 1)$ et $p$ est premier avec $a$ , donc, par le théorème de Gauss, $p$ divise $a^{p - 1} - 1$ . $∎$

Réponse rédigée : reste de $7^{1000}$ modulo $13$ . $13$ est premier et ne divise pas $7$ : d’après le petit théorème de Fermat, $7^{12} \equiv 1 [13]$ . Or $1 000 = 12 \times 83 + 4$ , donc $7^{1000} = (7^{12})^{83} \times 7^{4} \equiv 7^{4} [13]$ . Enfin $7^{2} = 49 = 3 \times 13 + 10$ , soit $7^{2} \equiv - 3 [13]$ , et $7^{4} \equiv 9 [13]$ . Le reste est $9$ .

Avec la seconde forme. Pour tout entier $n$ , $n^{13} \equiv n [13]$ : $13$ divise $n^{13} - n$ , même lorsque $13$ divise $n$ . Par exemple $2^{13} - 2 = 8 190 = 13 \times 630$ .

Un témoin. $91$ est-il premier ? $2^{12} = 4 096 = 45 \times 91 + 1$ , donc $2^{12} \equiv 1 [91]$ . Comme $90 = 12 \times 7 + 6$ , $2^{90} \equiv 2^{6} = 64 [91]$ . Puisque $2^{90} ≢ 1 [91]$ , $91$ n’est pas premier : $2$ est un témoin, et en effet $91 = 7 \times 13$ .

Réflexe — Avant d’écrire « d’après le petit théorème de Fermat », je vérifie que le module $p$ est premier et qu’il ne divise pas $a$ ; puis je divise l’exposant par $p - 1$ et je garde le reste.

Attention — Le module doit être premier : $2^{14} = 16 384 = 1 092 \times 15 + 4$ , donc $2^{14} \equiv 4 [15]$ , et non $1$ , car $15$ n’est pas premier. Et l’exposant se réduit par division par $p - 1$ , pas par $p$ .

6 / 6

Pour aller plus loin

Division euclidienne et algorithme d’Euclide. Pour calculer le PGCD de grands entiers sans les décomposer, on enchaîne les divisions euclidiennes : voir Divisibilité, division euclidienne et PGCD.

Théorème de Gauss. Le lemme d’Euclide en est un cas particulier. Le théorème de Gauss, sa démonstration exigible et ses applications aux équations $a x + b y = c$ sont traités dans Théorèmes de Bézout et de Gauss.

Congruences. Les calculs modulo $n$ utilisés avec le petit théorème de Fermat (compatibilité avec les opérations, cycles des restes des puissances) sont détaillés dans Congruences.

Des questions encore ouvertes. Certaines questions très simples à énoncer restent sans réponse, comme l’existence d’une infinité de nombres premiers jumeaux, c’est-à-dire de couples $(p; p + 2)$ de nombres premiers, tels que $(11; 13)$ ou $(41; 43)$ .

À retenir

Un nombre premier a exactement deux diviseurs positifs, $1$ et lui-même ; $0$ et $1$ ne sont pas premiers, $2$ est le seul nombre premier pair.
Tout entier $n ⩾ 2$ a un diviseur premier ; s’il est composé, il en a un, $p$ , tel que $p^{2} ⩽ n$ : on ne teste que les nombres premiers jusqu’à $\sqrt{n}$ .
L’ensemble des nombres premiers est infini : $N = p_{1} \times \dots \times p_{r} + 1$ a un diviseur premier hors de toute liste finie $p_{1}, \dots, p_{r}$ .
Décomposition unique $n = p_{1}^{a_{1}} \times \dots \times p_{r}^{a_{r}}$ ; $(a_{1} + 1) \dots (a_{r} + 1)$ diviseurs positifs ; carré parfait si et seulement si tous les exposants sont pairs.
PGCD : exposants minimaux ; PPCM : exposants maximaux ; $pgcd (a; b) \times ppcm (a; b) = a b$ .
Petit théorème de Fermat : si $p$ est premier et ne divise pas $a$ , $a^{p - 1} \equiv 1 [p]$ ; pour tout entier $a$ , $a^{p} \equiv a [p]$ .

Questions fréquentes

Comment savoir si un entier est premier ?

On encadre l’entier n entre deux carrés consécutifs, puis on teste sa divisibilité par les seuls nombres premiers p tels que p² ≤ n. Pour 223 : 14² = 196 ≤ 223 < 225 = 15², on teste 2, 3, 5, 7, 11 et 13 ; aucun ne divise 223, donc 223 est premier. Inutile d’aller plus loin : un entier composé a toujours un diviseur premier inférieur ou égal à sa racine carrée.

Pourquoi 1 n’est-il pas un nombre premier ?

Un nombre premier a exactement deux diviseurs positifs, 1 et lui-même ; 1 n’en a qu’un seul. Ce choix garantit l’unicité de la décomposition en facteurs premiers : si 1 était premier, on pourrait écrire 6 = 2 × 3, mais aussi 6 = 1 × 2 × 3 ou 6 = 1 × 1 × 2 × 3, sans fin.

Comment démontrer qu’il existe une infinité de nombres premiers ?

Par l’absurde : si p₁, …, pᵣ étaient tous les nombres premiers, l’entier N = p₁ × … × pᵣ + 1 aurait un diviseur premier p, forcément dans la liste. Alors p diviserait le produit et N, donc leur différence 1 : impossible. C’est une démonstration exigible au programme de maths expertes.

Comment trouver le nombre de diviseurs d’un entier ?

On décompose l’entier en facteurs premiers, puis on multiplie les exposants augmentés de 1. Pour 1 225 = 5² × 7², on obtient (2 + 1)(2 + 1) = 9 diviseurs : un nombre impair, ce qui est normal, car 1 225 = 35² est un carré parfait.

Que dit le petit théorème de Fermat ?

Si p est un nombre premier qui ne divise pas l’entier a, alors a^(p − 1) ≡ 1 [p] ; et pour tout entier a, a^p ≡ a [p]. Il sert à trouver le reste d’une grande puissance : 10¹⁸ ≡ 1 [19], donc 10⁴⁰ = (10¹⁸)² × 10⁴ ≡ 10 000 [19], et comme 10 000 = 526 × 19 + 6, le reste de 10⁴⁰ modulo 19 est 6.

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