Arithmétique
Ce chapitre fait partie du programme de Terminale.
Ce chapitre donne les outils pour raisonner sur les entiers : divisibilité, restes, diviseurs communs et nombres premiers. Ces outils permettent de résoudre des équations en nombres entiers et sont à la base des méthodes de chiffrement utilisées pour sécuriser les communications.
Prérequis
- Calcul algébrique dans $\mathbb{Z}$ : développer, factoriser, manipuler des puissances
- Raisonnement par récurrence (simple et forte)
- Raisonnement par l'absurde et par contraposée
- Coefficients binomiaux $\binom{n}{k}$ et formule du binôme de Newton
- Notion de partie entière d'un réel
À la fin du chapitre, on sait
- Utiliser la divisibilité et ses propriétés de combinaison linéaire
- Effectuer une division euclidienne dans $\mathbb{Z}$ et justifier l'unicité du reste
- Calculer avec les congruences et déterminer le reste d'une puissance
- Calculer un PGCD avec l'algorithme d'Euclide et obtenir une relation de Bézout
- Appliquer les théorèmes de Bézout et de Gauss, résoudre une équation $ax+by=c$
- Décomposer un entier en facteurs premiers et tester la primalité
- Utiliser le petit théorème de Fermat
- Chiffrer et déchiffrer un message avec un chiffrement affine, comprendre le principe du RSA
1.Divisibilité dans Z et division euclidienne
Diviseur, multiple
Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$ s'il existe un entier relatif $k$ tel que $b = ka$.
On note $a \mid b$. On dit aussi que $a$ est un diviseur de $b$, ou que $b$ est un multiple de $a$.
Cas particuliers
- Tout entier divise $0$, car $0 = 0 \times a$.
- $1$ et $-1$ divisent tout entier.
- $a \mid b$ équivaut à $-a \mid b$ : les diviseurs vont par paires opposées.
- Si $b \neq 0$ et $a \mid b$, alors $|a| \leqslant |b|$. Un entier non nul n'a donc qu'un nombre fini de diviseurs.
Transitivité et combinaisons linéaires
Soient $a$, $b$, $c$ des entiers relatifs.
- Si $a \mid b$ et $b \mid c$, alors $a \mid c$.
- Si $a \mid b$ et $a \mid c$, alors pour tous entiers $u$ et $v$, $a \mid bu + cv$.
En particulier, si $a$ divise $b$ et $c$, alors $a$ divise $b+c$ et $b-c$.
Preuve
-
Il existe $k$ et $k'$ entiers tels que $b = ka$ et $c = k'b$. Alors $c = k'ka = (kk')a$ avec $kk' \in \mathbb{Z}$, donc $a \mid c$.
-
Il existe $k$ et $k'$ entiers tels que $b = ka$ et $c = k'a$. Alors $bu + cv = kau + k'av = (ku + k'v)a$ avec $ku + k'v \in \mathbb{Z}$, donc $a \mid bu+cv$.
Déterminer les entiers n tels que n + 2 divise 3n + 11
On cherche les entiers relatifs $n$ tels que $n+2 \mid 3n+11$.
- $n+2$ divise $n+2$, donc divise $3(n+2) = 3n+6$.
- Si $n+2 \mid 3n+11$, alors $n+2$ divise la différence $(3n+11)-(3n+6) = 5$.
- Donc $n+2 \in \{-5 ; -1 ; 1 ; 5\}$, c'est-à-dire $n \in \{-7 ; -3 ; -1 ; 3\}$.
Réciproquement, on vérifie : pour $n=3$, $5 \mid 20$ ; pour $n=-1$, $1 \mid 8$ ; pour $n=-3$, $-1 \mid 2$ ; pour $n=-7$, $-5 \mid -10$.
Les solutions sont $-7$, $-3$, $-1$ et $3$.
Trouver les n tels que une expression divise une autre
Pour trouver les entiers $n$ tels que $A(n) \mid B(n)$ :
- On cherche une combinaison $B(n) - q\,A(n)$ qui ne dépend plus de $n$ (ou qui est plus simple). On obtient une constante $c$.
- Comme $A(n)$ divise $A(n)$ et $B(n)$, il divise $c$.
- On liste les diviseurs (positifs et négatifs) de $c$ et on en déduit les valeurs possibles de $n$.
- On vérifie chaque valeur : l'étape 2 donne seulement une condition nécessaire.
Division euclidienne
Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$. Il existe un unique couple $(q ; r)$ d'entiers tel que $$a = bq + r \quad \text{et} \quad 0 \leqslant r < b.$$ $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.
Preuve de l'existence et de l'unicité
Existence. Soit $q = \lfloor a/b \rfloor$ la partie entière de $a/b$ : c'est l'unique entier tel que $q \leqslant \frac{a}{b} < q+1$. Comme $b > 0$, on multiplie par $b$ : $bq \leqslant a < bq + b$. On pose $r = a - bq$. Alors $0 \leqslant r < b$ et $a = bq + r$.
Unicité. Supposons $a = bq + r = bq' + r'$ avec $0 \leqslant r < b$ et $0 \leqslant r' < b$. Alors $b(q - q') = r' - r$. Or $-b < r' - r < b$, et $r'-r$ est un multiple de $b$. Le seul multiple de $b$ strictement compris entre $-b$ et $b$ est $0$. Donc $r = r'$, puis $b(q-q') = 0$ avec $b \neq 0$, donc $q = q'$.
Deux divisions euclidiennes
- Division de $2026$ par $7$ : $7 \times 289 = 2023$, donc $2026 = 7 \times 289 + 3$ avec $0 \leqslant 3 < 7$. Quotient $289$, reste $3$.
- Division de $-17$ par $5$ : $-17 = 5 \times (-4) + 3$ avec $0 \leqslant 3 < 5$. Quotient $-4$, reste $3$.
Le reste est toujours positif
L'égalité $-17 = 5 \times (-3) - 2$ est vraie, mais ce n'est pas la division euclidienne : le reste doit vérifier $0 \leqslant r < b$. Pour un dividende négatif, le quotient est « un cran plus bas » que ce que l'on croit.
Restes possibles
Dans la division par $b$, il y a exactement $b$ restes possibles : $0, 1, \dots, b-1$. Tout entier s'écrit donc sous l'une des formes $bk$, $bk+1$, …, $bk + (b-1)$ avec $k \in \mathbb{Z}$. Par exemple, tout entier est de la forme $2k$ ou $2k+1$, ou encore $3k$, $3k+1$ ou $3k+2$.
2.Congruences
Congruence modulo n
Soit $n$ un entier naturel, $n \geqslant 2$. Deux entiers relatifs $a$ et $b$ sont congrus modulo $n$ si $n$ divise $a - b$.
On note $a \equiv b \;[n]$ (on lit « $a$ congru à $b$ modulo $n$ »).
Lien avec la division euclidienne
Soit $n \geqslant 2$.
- $a \equiv b \;[n]$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
- Si $r$ est le reste de la division de $a$ par $n$, alors $a \equiv r \;[n]$ avec $0 \leqslant r < n$.
- $a \equiv 0 \;[n]$ si et seulement si $n \mid a$.
Preuve du point 1
Écrivons $a = nq + r$ et $b = nq' + r'$ avec $0 \leqslant r < n$ et $0 \leqslant r' < n$. Alors $a - b = n(q - q') + (r - r')$.
- Si $r = r'$, alors $a - b = n(q-q')$, donc $n \mid a-b$.
- Si $n \mid a - b$, alors $n$ divise $(a-b) - n(q-q') = r - r'$. Or $-n < r - r' < n$, donc $r - r' = 0$.
Compatibilité avec les opérations
Soit $n \geqslant 2$. Si $a \equiv b \;[n]$ et $c \equiv d \;[n]$, alors :
- $a + c \equiv b + d \;[n]$ et $a - c \equiv b - d \;[n]$ ;
- $ac \equiv bd \;[n]$ ;
- pour tout $k \in \mathbb{N}$, $a^k \equiv b^k \;[n]$.
La congruence est aussi réflexive ($a \equiv a$), symétrique et transitive (si $a \equiv b$ et $b \equiv c$, alors $a \equiv c$).
Preuve
On a $a - b = kn$ et $c - d = k'n$ avec $k, k' \in \mathbb{Z}$.
- $(a+c) - (b+d) = (k + k')n$, donc $a + c \equiv b + d \;[n]$. Même chose pour la différence.
- $ac - bd = a(c - d) + d(a - b) = (ak' + dk)n$, donc $ac \equiv bd \;[n]$.
- Pour les puissances, on raisonne par récurrence sur $k$. Pour $k = 0$ : $a^0 = 1 = b^0$. Si $a^k \equiv b^k \;[n]$, alors en multipliant cette congruence par $a \equiv b \;[n]$ (point précédent), on obtient $a^{k+1} \equiv b^{k+1} \;[n]$.
On ne divise pas une congruence
On peut multiplier une congruence, mais pas la simplifier en général.
Exemple : $4 \times 2 = 8$ et $4 \times 5 = 20$ ont le même reste $2$ modulo $6$, donc $4 \times 2 \equiv 4 \times 5 \;[6]$. Pourtant $2 \not\equiv 5 \;[6]$.
La simplification par $a$ est permise seulement si $a$ et $n$ sont premiers entre eux (voir le théorème de Gauss).
Reste de la division de 2^2026 par 7
On calcule les premières puissances de $2$ modulo $7$ : $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 = 8 \equiv 1 \;[7]$.
On divise l'exposant par $3$ : $2026 = 3 \times 675 + 1$. Donc $$2^{2026} = \left(2^3\right)^{675} \times 2 \equiv 1^{675} \times 2 \equiv 2 \;[7].$$ Comme $0 \leqslant 2 < 7$, le reste est $2$.
Déterminer le reste de a^k modulo n
- On remplace $a$ par son reste modulo $n$ (ou par un entier congru plus simple, éventuellement négatif comme $-1$).
- On calcule les puissances successives jusqu'à trouver un exposant $m$ tel que $a^m \equiv 1 \;[n]$ (ou $\equiv -1$).
- On effectue la division euclidienne $k = mq + s$ avec $0 \leqslant s < m$.
- On écrit $a^k = (a^m)^q \times a^s \equiv a^s \;[n]$.
- On conclut en donnant un reste entre $0$ et $n-1$.
Exemple : $3^4 = 81 \equiv 1 \;[10]$ et $2027 = 4 \times 506 + 3$, donc $3^{2027} \equiv 3^3 = 27 \equiv 7 \;[10]$. Le chiffre des unités de $3^{2027}$ est $7$.
Tableau de congruences : n² + n + 1 n'est jamais divisible par 5
On étudie tous les restes possibles de $n$ modulo $5$.
| $n \equiv \dots \;[5]$ | $0$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|---|
| $n^2 \equiv$ | $0$ | $1$ | $4$ | $4$ | $1$ |
| $n^2 + n + 1 \equiv$ | $1$ | $3$ | $2$ | $3$ | $1$ |
Pour $n \equiv 2$ : $4 + 2 + 1 = 7 \equiv 2$. Pour $n \equiv 3$ : $4 + 3 + 1 = 8 \equiv 3$. Pour $n \equiv 4$ : $1 + 4 + 1 = 6 \equiv 1$.
La dernière ligne ne contient jamais $0$ : pour tout entier $n$, $5$ ne divise pas $n^2 + n + 1$.
Une divisibilité pour tout n
Montrons que pour tout $n \in \mathbb{N}$, $7 \mid 3^{2n+1} + 2^{n+2}$.
$3^{2n+1} = 3 \times 9^n$ et $9 \equiv 2 \;[7]$, donc $3^{2n+1} \equiv 3 \times 2^n \;[7]$. De plus $2^{n+2} = 4 \times 2^n$. Ainsi $$3^{2n+1} + 2^{n+2} \equiv 3 \times 2^n + 4 \times 2^n = 7 \times 2^n \equiv 0 \;[7].$$
Critères de divisibilité
Comme $10 \equiv 1 \;[9]$, on a $10^k \equiv 1 \;[9]$ pour tout $k$ : un entier est congru modulo $9$ à la somme de ses chiffres. Par exemple $2025 \equiv 2+0+2+5 = 9 \equiv 0 \;[9]$, donc $9 \mid 2025$.
Comme $10 \equiv -1 \;[11]$, un entier est congru modulo $11$ à la somme alternée de ses chiffres, en partant des unités.
3.PGCD et algorithme d'Euclide
PGCD, entiers premiers entre eux
Soient $a$ et $b$ deux entiers relatifs non tous deux nuls. L'ensemble de leurs diviseurs communs est fini et contient $1$. Son plus grand élément est le plus grand commun diviseur de $a$ et $b$, noté $\mathrm{PGCD}(a, b)$. C'est un entier naturel non nul.
On dit que $a$ et $b$ sont premiers entre eux si $\mathrm{PGCD}(a,b) = 1$, c'est-à-dire si leurs seuls diviseurs communs sont $1$ et $-1$.
Propriétés de calcul
Soient $a$ et $b$ des entiers non tous deux nuls.
- $\mathrm{PGCD}(a, b) = \mathrm{PGCD}(b, a) = \mathrm{PGCD}(|a|, |b|)$.
- Si $a \neq 0$, $\mathrm{PGCD}(a, 0) = |a|$.
- Si $b \mid a$ avec $b \neq 0$, alors $\mathrm{PGCD}(a, b) = |b|$.
- Pour tout entier $q$, $\mathrm{PGCD}(a, b) = \mathrm{PGCD}(b, a - bq)$. En particulier, si $r$ est le reste de la division euclidienne de $a$ par $b > 0$, alors $\mathrm{PGCD}(a, b) = \mathrm{PGCD}(b, r)$.
Preuve du point 4
On montre que les couples $(a, b)$ et $(b, a - bq)$ ont exactement les mêmes diviseurs communs.
- Si $d \mid a$ et $d \mid b$, alors $d$ divise la combinaison $a - bq$. Donc $d$ est un diviseur commun de $b$ et $a - bq$.
- Si $d \mid b$ et $d \mid a - bq$, alors $d$ divise $(a - bq) + qb = a$. Donc $d$ est un diviseur commun de $a$ et $b$.
Les deux ensembles de diviseurs communs sont égaux, donc ils ont le même plus grand élément.
Algorithme d'Euclide
Pour calculer $\mathrm{PGCD}(a, b)$ avec $a \geqslant b > 0$ :
- On effectue la division euclidienne de $a$ par $b$ : $a = bq_1 + r_1$.
- Si $r_1 = 0$, le PGCD est $b$. Sinon, on recommence avec le couple $(b, r_1)$, puis $(r_1, r_2)$, etc.
- Les restes forment une suite d'entiers naturels strictement décroissante, donc on atteint un reste nul après un nombre fini d'étapes.
- Le PGCD est le dernier reste non nul.
En effet, par la propriété précédente : $\mathrm{PGCD}(a,b) = \mathrm{PGCD}(b, r_1) = \mathrm{PGCD}(r_1, r_2) = \dots = \mathrm{PGCD}(r_k, 0) = r_k$.
Calcul de PGCD(1071, 462)
$$\begin{aligned} 1071 &= 2 \times 462 + 147 \\ 462 &= 3 \times 147 + 21 \\ 147 &= 7 \times 21 + 0 \end{aligned}$$ Le dernier reste non nul est $21$, donc $\mathrm{PGCD}(1071, 462) = 21$.
Programmation
L'algorithme d'Euclide se programme en quelques lignes en Python (l'opérateur % donne le reste de la division euclidienne) :
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a
PGCD de deux expressions en n
Soit $n \in \mathbb{N}$. On cherche $\mathrm{PGCD}(2n+3, n+1)$.
Par la propriété 4 avec $q = 2$ : $\mathrm{PGCD}(2n+3, n+1) = \mathrm{PGCD}(n+1, (2n+3) - 2(n+1)) = \mathrm{PGCD}(n+1, 1) = 1$.
Donc $2n+3$ et $n+1$ sont premiers entre eux pour tout $n$. De même, deux entiers consécutifs $n$ et $n+1$ sont toujours premiers entre eux.
4.Théorème de Bézout et théorème de Gauss
Identité de Bézout
Soient $a$ et $b$ deux entiers relatifs non tous deux nuls, et $d = \mathrm{PGCD}(a, b)$. Il existe deux entiers relatifs $u$ et $v$ tels que $$au + bv = d.$$
Preuve
Soit $E$ l'ensemble des entiers strictement positifs de la forme $au + bv$ avec $u, v \in \mathbb{Z}$. $E$ est non vide : il contient $a^2 + b^2 = a \times a + b \times b > 0$. Toute partie non vide de $\mathbb{N}$ admet un plus petit élément ; notons $m = au_0 + bv_0$ le plus petit élément de $E$.
$m$ divise $a$. On écrit la division euclidienne $a = mq + r$ avec $0 \leqslant r < m$. Alors $r = a - q(au_0 + bv_0) = a(1 - qu_0) + b(-qv_0)$. Si $r > 0$, alors $r \in E$ et $r < m$, ce qui contredit la minimalité de $m$. Donc $r = 0$ et $m \mid a$. De même, $m \mid b$.
$m$ est le PGCD. $m$ est un diviseur commun positif de $a$ et $b$, donc $m \leqslant d$. Par ailleurs $d$ divise $a$ et $b$, donc $d$ divise $au_0 + bv_0 = m$, d'où $d \leqslant m$. Ainsi $m = d$ et $d = au_0 + bv_0$.
Théorème de Bézout
Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $u$ et $v$ tels que $$au + bv = 1.$$
Preuve
- Si $\mathrm{PGCD}(a, b) = 1$, l'identité de Bézout fournit $u$ et $v$ tels que $au + bv = 1$.
- Réciproquement, supposons $au + bv = 1$. Tout diviseur commun positif $d$ de $a$ et $b$ divise $au + bv = 1$, donc $d = 1$. Ainsi $\mathrm{PGCD}(a,b) = 1$.
La réciproque ne vaut que pour 1
Si $au + bv = d$, on ne peut pas conclure que $d = \mathrm{PGCD}(a,b)$ lorsque $d \neq 1$. Exemple : $2 \times 4 + 3 \times (-2) = 2$, alors que $\mathrm{PGCD}(2, 3) = 1$. On peut seulement dire que $\mathrm{PGCD}(a,b)$ divise $d$.
Obtenir des coefficients de Bézout
- On applique l'algorithme d'Euclide à $a$ et $b$.
- On écrit chaque reste non nul sous la forme « reste = dividende − quotient × diviseur ».
- On part de l'égalité donnant le PGCD (avant-dernière ligne) et on remplace successivement chaque reste par son expression, en remontant, jusqu'à n'avoir plus que $a$ et $b$.
- On vérifie le résultat par un calcul direct.
Exemple avec $1071$ et $462$ : $21 = 462 - 3 \times 147$ et $147 = 1071 - 2 \times 462$, donc $21 = 462 - 3(1071 - 2 \times 462) = 7 \times 462 - 3 \times 1071$. Vérification : $3234 - 3213 = 21$.
Relation de Bézout entre 59 et 27
Algorithme d'Euclide : $$\begin{aligned} 59 &= 2 \times 27 + 5 \\ 27 &= 5 \times 5 + 2 \\ 5 &= 2 \times 2 + 1 \\ 2 &= 2 \times 1 + 0 \end{aligned}$$ Donc $\mathrm{PGCD}(59, 27) = 1$. On remonte : $$\begin{aligned} 1 &= 5 - 2 \times 2 \\ &= 5 - 2(27 - 5 \times 5) = 11 \times 5 - 2 \times 27 \\ &= 11(59 - 2 \times 27) - 2 \times 27 = 11 \times 59 - 24 \times 27. \end{aligned}$$ Vérification : $11 \times 59 = 649$ et $24 \times 27 = 648$, la différence vaut $1$.
Conséquences de l'identité de Bézout
Soient $a, b$ non tous deux nuls et $d = \mathrm{PGCD}(a,b)$.
- Les diviseurs communs de $a$ et $b$ sont exactement les diviseurs de $d$.
- Il existe $a'$ et $b'$ entiers premiers entre eux tels que $a = da'$ et $b = db'$.
Preuve. 1. Un diviseur de $d$ divise $a$ et $b$ car $d$ les divise. Un diviseur commun de $a$ et $b$ divise $au + bv = d$. 2. $d$ divise $a$ et $b$, d'où $a'$ et $b'$. En divisant $au + bv = d$ par $d \neq 0$ : $a'u + b'v = 1$, donc $a'$ et $b'$ sont premiers entre eux par le théorème de Bézout.
Théorème de Gauss
Soient $a$, $b$, $c$ trois entiers relatifs. Si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.
Preuve
Comme $\mathrm{PGCD}(a, b) = 1$, le théorème de Bézout donne $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. On multiplie par $c$ : $$c = acu + bcv.$$ $a$ divise $acu$, et $a$ divise $bc$ donc $bcv$. Par combinaison linéaire, $a$ divise $acu + bcv = c$.
Corollaire : produit de diviseurs premiers entre eux
Si $a$ et $b$ divisent $n$ et si $a$ et $b$ sont premiers entre eux, alors $ab$ divise $n$.
Preuve. $a \mid n$ donc $n = ak$ avec $k \in \mathbb{Z}$. Alors $b \mid ak$ et $\mathrm{PGCD}(b, a) = 1$, donc $b \mid k$ par le théorème de Gauss : $k = bk'$. Ainsi $n = abk'$ et $ab \mid n$.
Exemple : un entier divisible par $3$ et par $4$ est divisible par $12$. En revanche, $12$ est divisible par $4$ et par $6$ mais pas par $24$ : l'hypothèse « premiers entre eux » est indispensable.
Inverse modulo n
Soit $n \geqslant 2$ et $a \in \mathbb{Z}$. Il existe un entier $a'$ tel que $aa' \equiv 1 \;[n]$ si et seulement si $a$ et $n$ sont premiers entre eux. On dit que $a'$ est un inverse de $a$ modulo $n$.
Preuve. $aa' \equiv 1 \;[n]$ équivaut à l'existence de $k \in \mathbb{Z}$ tel que $aa' - 1 = kn$, c'est-à-dire $aa' + n(-k) = 1$. Par le théorème de Bézout, un tel couple existe si et seulement si $\mathrm{PGCD}(a, n) = 1$.
Résoudre 3x ≡ 4 [7]
$3 \times 5 = 15 \equiv 1 \;[7]$, donc $5$ est un inverse de $3$ modulo $7$.
- Si $3x \equiv 4 \;[7]$, en multipliant par $5$ : $15x \equiv 20 \;[7]$, soit $x \equiv 6 \;[7]$.
- Réciproquement, si $x \equiv 6 \;[7]$, alors $3x \equiv 18 \equiv 4 \;[7]$.
Les solutions sont les entiers $x = 6 + 7k$, $k \in \mathbb{Z}$.
Équation ax + by = c
Soient $a, b$ non tous deux nuls, $d = \mathrm{PGCD}(a,b)$ et $c \in \mathbb{Z}$. L'équation $ax + by = c$ admet des solutions entières si et seulement si $d$ divise $c$.
Preuve. Si $(x, y)$ est solution, $d$ divise $a$ et $b$ donc divise $ax + by = c$. Réciproquement, si $c = dk$, l'identité de Bézout $au + bv = d$ donne $a(uk) + b(vk) = c$.
Résoudre une équation diophantienne ax + by = c
- On calcule $d = \mathrm{PGCD}(a, b)$. Si $d \nmid c$, il n'y a pas de solution. Sinon, on divise l'équation par $d$ pour se ramener à $a$ et $b$ premiers entre eux.
- On trouve une solution particulière $(x_0, y_0)$ : évidente, ou à partir d'une relation de Bézout multipliée par $c$.
- On soustrait : $a(x - x_0) = -b(y - y_0)$.
- $a$ divise $b(y - y_0)$ et $\mathrm{PGCD}(a,b) = 1$, donc $a \mid y - y_0$ par Gauss. On en déduit $y$, puis $x$, en fonction d'un entier $k$.
- On vérifie que tous les couples obtenus sont bien solutions (réciproque).
Résoudre 11x − 7y = 5 dans Z²
$\mathrm{PGCD}(11, 7) = 1$. On remarque $11 \times 2 - 7 \times 3 = 1$. En multipliant par $5$ : $11 \times 10 - 7 \times 15 = 5$. Donc $(10 ; 15)$ est solution.
Si $(x, y)$ est solution, par différence : $11(x - 10) - 7(y - 15) = 0$, soit $11(x - 10) = 7(y - 15)$.
$7$ divise $11(x - 10)$ et $\mathrm{PGCD}(7, 11) = 1$, donc par le théorème de Gauss $7 \mid x - 10$ : $x = 10 + 7k$ avec $k \in \mathbb{Z}$. En reportant : $11 \times 7k = 7(y - 15)$, d'où $y = 15 + 11k$.
Réciproquement, $11(10 + 7k) - 7(15 + 11k) = 110 - 105 + 77k - 77k = 5$.
Les solutions sont les couples $(10 + 7k ; 15 + 11k)$, $k \in \mathbb{Z}$. En remplaçant $k$ par $k - 1$, on peut aussi les écrire $(3 + 7k ; 4 + 11k)$.
5.Nombres premiers
Nombre premier
Un entier naturel $p$ est premier s'il admet exactement deux diviseurs positifs : $1$ et $p$.
$0$ et $1$ ne sont pas premiers. Les premiers nombres premiers sont $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \dots$ Le seul nombre premier pair est $2$.
Un entier $n \geqslant 2$ non premier est dit composé : il s'écrit $n = ab$ avec $2 \leqslant a \leqslant b \leqslant n - 1$.
Plus petit diviseur
Soit $n \geqslant 2$.
- Le plus petit diviseur de $n$ supérieur ou égal à $2$ est un nombre premier. En particulier, tout entier $n \geqslant 2$ admet au moins un diviseur premier.
- Si $n$ n'est pas premier, il admet un diviseur premier $p$ tel que $p^2 \leqslant n$, c'est-à-dire $p \leqslant \sqrt{n}$.
Preuve
-
L'ensemble des diviseurs de $n$ supérieurs ou égaux à $2$ est non vide (il contient $n$) ; soit $p$ son plus petit élément. Si $p$ n'était pas premier, il aurait un diviseur $d$ avec $2 \leqslant d < p$. Par transitivité, $d$ diviserait $n$, ce qui contredit la minimalité de $p$. Donc $p$ est premier.
-
Si $n$ n'est pas premier, son plus petit diviseur $p \geqslant 2$ vérifie $p < n$ et $n = pm$ avec $m \geqslant 2$. Comme $m$ est aussi un diviseur de $n$ supérieur ou égal à $2$, on a $m \geqslant p$. Donc $n = pm \geqslant p^2$.
Tester si un entier est premier
Pour savoir si $n \geqslant 2$ est premier :
- On calcule (ou on encadre) $\sqrt{n}$.
- On teste la divisibilité de $n$ par chaque nombre premier $p \leqslant \sqrt{n}$.
- Si aucun ne divise $n$, alors $n$ est premier (par contraposée de la propriété 2). Si l'un d'eux divise $n$, $n$ est composé.
211 et 221
- $\sqrt{211} \approx 14{,}5$. On teste $2, 3, 5, 7, 11, 13$ : $211$ est impair ; la somme des chiffres vaut $4$, donc $3 \nmid 211$ ; il ne finit pas par $0$ ou $5$ ; $211 = 7 \times 30 + 1$ ; $211 = 11 \times 19 + 2$ ; $211 = 13 \times 16 + 3$. Aucun ne divise $211$ : $211$ est premier.
- $\sqrt{221} \approx 14{,}9$. Les tests par $2, 3, 5, 7, 11$ échouent, mais $221 = 13 \times 17$ : $221$ n'est pas premier.
Infinité des nombres premiers
Il existe une infinité de nombres premiers.
Preuve (Euclide)
On raisonne par l'absurde. Supposons qu'il n'existe qu'un nombre fini de nombres premiers $p_1, p_2, \dots, p_k$. On pose $$N = p_1 p_2 \cdots p_k + 1.$$ $N \geqslant 2$, donc $N$ admet un diviseur premier, qui est l'un des $p_i$. Alors $p_i$ divise $N$ et divise $p_1 p_2 \cdots p_k$, donc il divise la différence $N - p_1 \cdots p_k = 1$. C'est impossible car $p_i \geqslant 2$. Il y a donc une infinité de nombres premiers.
Lemme d'Euclide
Soit $p$ un nombre premier et $a$, $b$ des entiers. Si $p$ divise $ab$, alors $p$ divise $a$ ou $p$ divise $b$.
Preuve. Supposons que $p$ ne divise pas $a$. Les diviseurs positifs de $p$ sont $1$ et $p$, et $p$ ne divise pas $a$, donc $\mathrm{PGCD}(p, a) = 1$. Comme $p \mid ab$, le théorème de Gauss donne $p \mid b$.
Par récurrence, si $p$ divise un produit $a_1 a_2 \cdots a_k$, il divise l'un des facteurs. En particulier, si $p \mid a^k$, alors $p \mid a$.
Décomposition en produit de facteurs premiers
Tout entier $n \geqslant 2$ s'écrit comme un produit de nombres premiers : $$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$ où $p_1 < p_2 < \dots < p_k$ sont des nombres premiers et $\alpha_1, \dots, \alpha_k$ des entiers naturels non nuls. Cette écriture est unique (l'unicité est admise).
Preuve de l'existence
Par récurrence forte sur $n \geqslant 2$.
- $2$ est premier, c'est un produit à un seul facteur.
- Soit $n \geqslant 3$ ; supposons que tout entier $m$ avec $2 \leqslant m \leqslant n - 1$ est un produit de nombres premiers. Si $n$ est premier, c'est terminé. Sinon, $n = ab$ avec $2 \leqslant a \leqslant n-1$ et $2 \leqslant b \leqslant n-1$. Par hypothèse de récurrence, $a$ et $b$ sont des produits de nombres premiers, donc $n = ab$ aussi.
Par récurrence forte, la propriété est vraie pour tout $n \geqslant 2$.
Diviseurs d'un entier décomposé
Si $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, les diviseurs positifs de $n$ sont les entiers $p_1^{\beta_1} \cdots p_k^{\beta_k}$ avec $0 \leqslant \beta_i \leqslant \alpha_i$ pour tout $i$.
Le nombre de diviseurs positifs de $n$ est donc $(\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$.
Le PGCD de deux entiers s'obtient en prenant les facteurs premiers communs, chacun avec le plus petit des deux exposants.
Décomposition de 360 et de 84
$360 = 2 \times 180 = 2^2 \times 90 = 2^3 \times 45 = 2^3 \times 3^2 \times 5$.
Nombre de diviseurs positifs de $360$ : $(3+1)(2+1)(1+1) = 24$.
$84 = 2^2 \times 3 \times 7$. Facteurs communs : $2$ (exposants $3$ et $2$) et $3$ (exposants $2$ et $1$). Donc $\mathrm{PGCD}(360, 84) = 2^2 \times 3 = 12$. Vérification : $360 = 12 \times 30$ et $84 = 12 \times 7$, avec $30$ et $7$ premiers entre eux.
Crible d'Ératosthène
Pour lister les nombres premiers jusqu'à $N$, on écrit les entiers de $2$ à $N$, puis on barre les multiples stricts de $2$, de $3$, de $5$, etc. Il suffit de le faire pour les nombres premiers $p \leqslant \sqrt{N}$. Les entiers non barrés sont les nombres premiers.
6.Petit théorème de Fermat
Lemme : p divise les coefficients binomiaux intermédiaires
Soit $p$ un nombre premier. Pour tout entier $k$ tel que $1 \leqslant k \leqslant p - 1$, $p$ divise $\binom{p}{k}$.
Preuve
On utilise la relation $k\binom{p}{k} = p\binom{p-1}{k-1}$, valable pour $1 \leqslant k \leqslant p$. Elle s'obtient avec les factorielles : $$k \binom{p}{k} = k \times \frac{p!}{k!\,(p-k)!} = \frac{p \times (p-1)!}{(k-1)!\,(p-k)!} = p \binom{p-1}{k-1}.$$ Ainsi $p$ divise $k\binom{p}{k}$. Comme $1 \leqslant k \leqslant p-1$, $p$ premier ne divise pas $k$, donc $\mathrm{PGCD}(p, k) = 1$. Par le théorème de Gauss, $p$ divise $\binom{p}{k}$.
Petit théorème de Fermat
Soit $p$ un nombre premier et $a$ un entier relatif.
- $a^p \equiv a \;[p]$.
- Si de plus $p$ ne divise pas $a$, alors $a^{p-1} \equiv 1 \;[p]$.
Preuve
Point 1 pour $a \in \mathbb{N}$, par récurrence sur $a$.
- Pour $a = 0$ : $0^p = 0$.
- Supposons $a^p \equiv a \;[p]$. Par la formule du binôme : $$(a + 1)^p = a^p + \sum_{k=1}^{p-1} \binom{p}{k} a^k + 1.$$ D'après le lemme, chaque terme de la somme est divisible par $p$. Donc $(a+1)^p \equiv a^p + 1 \equiv a + 1 \;[p]$ par hypothèse de récurrence.
Point 1 pour $a \in \mathbb{Z}$. Soit $r$ le reste de la division de $a$ par $p$ : $a \equiv r \;[p]$ avec $r \in \mathbb{N}$. Alors $a^p \equiv r^p \equiv r \equiv a \;[p]$.
Point 2. D'après le point 1, $p$ divise $a^p - a = a(a^{p-1} - 1)$. Comme $p$ est premier et ne divise pas $a$, le lemme d'Euclide donne $p \mid a^{p-1} - 1$, c'est-à-dire $a^{p-1} \equiv 1 \;[p]$.
Reste de 3^100 modulo 7
$7$ est premier et ne divise pas $3$, donc $3^6 \equiv 1 \;[7]$ (on peut vérifier : $3^6 = 729 = 7 \times 104 + 1$).
$100 = 6 \times 16 + 4$, donc $3^{100} = (3^6)^{16} \times 3^4 \equiv 3^4 = 81 \;[7]$. Or $81 = 7 \times 11 + 4$.
Le reste de $3^{100}$ dans la division par $7$ est $4$.
Utiliser le petit théorème de Fermat
Pour calculer $a^k$ modulo un nombre premier $p$ qui ne divise pas $a$ :
- On vérifie que $p$ est premier et que $p \nmid a$.
- On écrit $a^{p-1} \equiv 1 \;[p]$.
- On divise $k$ par $p - 1$ : $k = (p-1)q + s$ avec $0 \leqslant s < p-1$.
- On conclut : $a^k \equiv a^s \;[p]$.
L'exposant $p-1$ fonctionne toujours, mais un exposant plus petit peut aussi convenir (par exemple $2^3 \equiv 1 \;[7]$).
n⁵ − n est divisible par 30
Soit $n \in \mathbb{Z}$.
- $5$ est premier, donc par le petit théorème de Fermat $n^5 \equiv n \;[5]$ : $5 \mid n^5 - n$.
- $n^5 - n = n(n^4 - 1) = n(n^2-1)(n^2+1) = (n-1)n(n+1)(n^2+1)$. Le produit $(n-1)n(n+1)$ de trois entiers consécutifs contient un multiple de $2$ et un multiple de $3$, donc $2 \mid n^5 - n$ et $3 \mid n^5 - n$.
- $2$ et $3$ sont premiers entre eux, donc $6 \mid n^5 - n$ (corollaire de Gauss). Puis $6$ et $5$ sont premiers entre eux, donc $30 \mid n^5 - n$.
La réciproque est fausse
Si $a^{n-1} \equiv 1 \;[n]$, on ne peut pas conclure que $n$ est premier.
Exemple : $2^{10} = 1024 = 3 \times 341 + 1$, donc $2^{10} \equiv 1 \;[341]$, puis $2^{340} = (2^{10})^{34} \equiv 1 \;[341]$. Pourtant $341 = 11 \times 31$ n'est pas premier.
En revanche, la contraposée est vraie et utile : si $a^{n-1} \not\equiv 1 \;[n]$ pour un $a$ premier avec $n$, alors $n$ n'est pas premier.
Inverse modulo un nombre premier
Si $p$ est premier et $p \nmid a$, alors $a \times a^{p-2} = a^{p-1} \equiv 1 \;[p]$ : $a^{p-2}$ est un inverse de $a$ modulo $p$. Par exemple, modulo $7$, un inverse de $3$ est $3^5 = 243 \equiv 5 \;[7]$, ce qui est cohérent avec $3 \times 5 = 15 \equiv 1 \;[7]$.
7.Applications au chiffrement
Chiffrer un message, c'est le transformer pour qu'il ne soit lisible que par son destinataire. On remplace chaque lettre par un nombre, on applique une fonction de chiffrement, et le destinataire applique la fonction réciproque. Les congruences fournissent des fonctions faciles à calculer, et les théorèmes de Bézout et de Fermat garantissent que le déchiffrement est possible.
On numérote les lettres de $0$ à $25$ :
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
Chiffrement affine
Soient $a$ et $b$ deux entiers. Le chiffrement affine de clé $(a, b)$ associe à la lettre de rang $x$ la lettre de rang $y$, où $y$ est le reste de la division euclidienne de $ax + b$ par $26$ : $$y \equiv ax + b \;[26], \quad 0 \leqslant y \leqslant 25.$$
Condition de déchiffrement
Le chiffrement affine de clé $(a, b)$ permet de retrouver chaque lettre (deux lettres distinctes sont codées différemment) si et seulement si $a$ et $26$ sont premiers entre eux.
Dans ce cas, si $a'$ est un inverse de $a$ modulo $26$, le déchiffrement est donné par $$x \equiv a'(y - b) \;[26].$$
Preuve
- Si $\mathrm{PGCD}(a, 26) = 1$, il existe $a'$ tel que $aa' \equiv 1 \;[26]$. Si $y \equiv ax + b \;[26]$, alors $a'(y - b) \equiv a'ax \equiv x \;[26]$. Comme $0 \leqslant x \leqslant 25$, $x$ est le reste de $a'(y-b)$ modulo $26$ : il est entièrement déterminé par $y$.
- Si $d = \mathrm{PGCD}(a, 26) \geqslant 2$, posons $x_1 = 26/d$, avec $1 \leqslant x_1 \leqslant 13$. Alors $ax_1 = 26 \times \frac{a}{d} \equiv 0 \;[26]$, donc les lettres de rangs $0$ et $x_1$ sont toutes deux codées par la lettre de rang $b$ modulo $26$ : le déchiffrement est impossible.
Chiffrer et déchiffrer avec la clé (5 ; 3)
$\mathrm{PGCD}(5, 26) = 1$, la clé est valable. On chiffre le mot MATH avec $y \equiv 5x + 3 \;[26]$ :
| Lettre | M | A | T | H |
|---|---|---|---|---|
| $x$ | 12 | 0 | 19 | 7 |
| $5x + 3$ | 63 | 3 | 98 | 38 |
| $y$ | 11 | 3 | 20 | 12 |
| Lettre codée | L | D | U | M |
MATH est codé LDUM.
Pour déchiffrer : $5 \times 21 = 105 = 4 \times 26 + 1$, donc $21$ est un inverse de $5$ modulo $26$. On utilise $x \equiv 21(y - 3) \;[26]$. Pour L ($y = 11$) : $21 \times 8 = 168 = 6 \times 26 + 12$, donc $x = 12$, soit M. Pour U ($y = 20$) : $21 \times 17 = 357 = 13 \times 26 + 19$, donc $x = 19$, soit T.
Déchiffrer un message codé par un chiffrement affine
- On vérifie que $\mathrm{PGCD}(a, 26) = 1$.
- On cherche un inverse $a'$ de $a$ modulo $26$ : par essais, ou avec une relation de Bézout $au + 26v = 1$ (alors $a' = u$).
- On montre l'équivalence $y \equiv ax + b \;[26] \iff x \equiv a'(y - b) \;[26]$ (multiplication par $a'$ dans un sens, par $a$ dans l'autre).
- Pour chaque lettre codée, on calcule le reste de $a'(y - b)$ modulo $26$.
Principe du chiffrement RSA
Soient $p$ et $q$ deux nombres premiers distincts, $n = pq$, et $e$, $d$ deux entiers naturels non nuls tels que $ed \equiv 1 \;[(p-1)(q-1)]$. Alors pour tout entier $m$ : $$m^{ed} \equiv m \;[n].$$ On chiffre un message $m$ (avec $0 \leqslant m < n$) en calculant le reste $c$ de $m^e$ modulo $n$. On déchiffre en calculant le reste de $c^d$ modulo $n$, qui redonne $m$. Le couple $(n, e)$ est public, $d$ est secret.
Preuve
On écrit $ed = 1 + k(p-1)(q-1)$ avec $k \in \mathbb{N}$.
- Si $p \nmid m$, le petit théorème de Fermat donne $m^{p-1} \equiv 1 \;[p]$, donc $m^{ed} = m \times \left(m^{p-1}\right)^{k(q-1)} \equiv m \;[p]$.
- Si $p \mid m$, alors $m \equiv 0 \;[p]$ et $m^{ed} \equiv 0 \equiv m \;[p]$.
Dans tous les cas, $p \mid m^{ed} - m$. De même, $q \mid m^{ed} - m$. Comme $p$ et $q$ sont des nombres premiers distincts, ils sont premiers entre eux, donc $pq \mid m^{ed} - m$ (corollaire de Gauss).
Un RSA miniature
$p = 5$, $q = 11$, $n = 55$, $(p-1)(q-1) = 40$. On choisit $e = 3$ ; on cherche $d$ tel que $3d \equiv 1 \;[40]$ : $3 \times 27 = 81 = 2 \times 40 + 1$, donc $d = 27$.
Chiffrement de $m = 7$ : $7^3 = 343 = 6 \times 55 + 13$, donc $c = 13$.
Déchiffrement : on calcule $13^{27}$ modulo $55$. $13^2 = 169 = 3 \times 55 + 4$, donc $13^{27} = 13 \times (13^2)^{13} \equiv 13 \times 4^{13} = 13 \times 2^{26}$. Or $2^{10} = 1024 = 18 \times 55 + 34$ et $34^2 = 1156 = 21 \times 55 + 1$, donc $2^{20} \equiv 1 \;[55]$. Ainsi $2^{26} \equiv 2^6 = 64 \equiv 9 \;[55]$ et $13^{27} \equiv 13 \times 9 = 117 \equiv 7 \;[55]$. On retrouve bien $m = 7$.
Sécurité
Connaître $d$ revient en pratique à connaître $p$ et $q$. La sécurité du RSA repose sur la difficulté de factoriser $n$ lorsque $p$ et $q$ ont plusieurs centaines de chiffres, alors que les calculs de puissances modulo $n$ restent rapides. Le chiffrement affine, lui, se casse facilement : il n'y a que $12 \times 26 = 312$ clés possibles. Le RSA n'est pas un attendu du programme, il illustre l'usage du petit théorème de Fermat.