À propos de cette page
Ce cours de maths complémentaires (option tle) en terminale sur « Arithmétique » suit le programme officiel de maths complémentaires (option tle) de terminale. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : Divisibilité dans ℤ, Division euclidienne, PGCD et algorithme d'Euclide, Nombres premiers. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de terminale à réussir en maths complémentaires (option tle).
Au programme
1 · Divisibilité dans ℤ
2 · Division euclidienne
3 · PGCD et algorithme d'Euclide
4 · Nombres premiers
5 · Théorème de Bézout et identité de Bézout
6 · Congruences
7 · Applications : cryptographie et calendriers
1Divisibilité dans ℤ
On travaille dans l'ensemble $\mathbb{Z}$ des entiers relatifs.
Définition. Soient $a, b \in \mathbb{Z}$ avec $b \neq 0$. On dit que $b$ divise $a$ (ou que $a$ est un multiple de $b$), et on note $b \mid a$, s'il existe $k \in \mathbb{Z}$ tel que $a = kb$.
Exemples.- $3 \mid 12$ car $12 = 4 \times 3$.
- $7 \mid (-35)$ car $-35 = (-5) \times 7$.
- $5 \nmid 13$ car il n'existe pas d'entier $k$ tel que $13 = 5k$.
Propriétés de la divisibilité.- Si $b \mid a$ et $b \mid c$, alors $b \mid (a+c)$ et $b \mid (a-c)$.
- Si $b \mid a$, alors $b \mid ka$ pour tout $k \in \mathbb{Z}$.
- Si $b \mid a$ et $a \mid c$, alors $b \mid c$ (transitivité).
Attention ! $b \mid a$ ne signifie pas que $a \mid b$. Par exemple $3 \mid 12$ mais $12 \nmid 3$.
2Division euclidienne
Théorème (Division euclidienne). Pour tous $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$, il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que $$a = bq + r \quad \text{et} \quad 0 \leq r < |b|.$$ On appelle $q$ le quotient et $r$ le reste de la division de $a$ par $b$.
Exemples.- $127 = 9 \times 14 + 1$ : le quotient de $127$ par $9$ est $14$, le reste est $1$.
- $-17 = 5 \times (-4) + 3$ : le quotient de $-17$ par $5$ est $-4$, le reste est $3$.
Lien avec la divisibilité. $b \mid a \iff$ le reste de la division euclidienne de $a$ par $b$ est $0$.
Division euclidienne : $a = bq + r$, avec $0 \leq r < |b|$.
3PGCD et algorithme d'Euclide
Définition. Le Plus Grand Commun Diviseur (PGCD) de deux entiers $a$ et $b$ (non tous les deux nuls) est le plus grand entier strictement positif qui divise à la fois $a$ et $b$. On le note $\text{PGCD}(a,b)$ ou $a \wedge b$.
Algorithme d'Euclide. Pour calculer $\text{PGCD}(a,b)$ avec $a \geq b > 0$ :
- Effectuer la division euclidienne de $a$ par $b$ : $a = bq_1 + r_1$.
- Si $r_1 = 0$, alors $\text{PGCD}(a,b) = b$.
- Sinon remplacer $(a,b)$ par $(b, r_1)$ et recommencer.
Exemple. Calculons $\text{PGCD}(252, 105)$ :
- $252 = 105 \times 2 + 42$
- $105 = 42 \times 2 + 21$
- $42 = 21 \times 2 + 0$ ← reste nul
Donc $\text{PGCD}(252, 105) = 21$.
Déroulement de l'algorithme d'Euclide pour PGCD(252, 105) = 21.
Propriété fondamentale. $\text{PGCD}(a,b) = \text{PGCD}(b, r)$ où $r$ est le reste de la division de $a$ par $b$.
Entiers premiers entre eux. $a$ et $b$ sont dits premiers entre eux (ou copremiers) si $\text{PGCD}(a,b) = 1$.
4Nombres premiers
Définition. Un entier $p \geq 2$ est premier s'il admet exactement deux diviseurs positifs : $1$ et lui-même.
Premiers nombres premiers. $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \ldots$
Théorème fondamental de l'arithmétique. Tout entier $n \geq 2$ s'écrit de façon unique (à l'ordre des facteurs près) comme produit de nombres premiers : $$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}.$$ C'est la décomposition en facteurs premiers.
Exemples.- $360 = 2^3 \times 3^2 \times 5$
- $1001 = 7 \times 11 \times 13$
Crible d'Ératosthène. Pour trouver tous les nombres premiers jusqu'à $N$ :
- Écrire tous les entiers de $2$ à $N$.
- Barrer tous les multiples de $2$ (sauf $2$), puis de $3$, puis de $5$, etc.
- Les nombres non barrés sont premiers.
On s'arrête quand le diviseur testé dépasse $\sqrt{N}$.
Attention ! $1$ n'est pas un nombre premier (il faut exactement deux diviseurs distincts).
PGCD via décomposition en facteurs premiers. Si $a = \prod p_i^{\alpha_i}$ et $b = \prod p_i^{\beta_i}$, alors $\text{PGCD}(a,b) = \prod p_i^{\min(\alpha_i,\beta_i)}$.
5Théorème de Bézout et identité de Bézout
Théorème de Bézout. Soient $a, b \in \mathbb{Z}$ non tous nuls, et $d = \text{PGCD}(a,b)$. Il existe $u, v \in \mathbb{Z}$ tels que $$au + bv = d.$$ En particulier, $a$ et $b$ sont premiers entre eux si et seulement s'il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$.
Méthode de remontée. On obtient $u$ et $v$ en « remontant » les étapes de l'algorithme d'Euclide.
Exemple. Trouvons $u, v$ tels que $252u + 105v = 21$ :
- D'après l'algorithme : $21 = 105 - 42 \times 2$
- Or $42 = 252 - 105 \times 2$
- Donc $21 = 105 - (252 - 105 \times 2) \times 2 = 105 \times 5 - 252 \times 2$
- Ainsi $u = -2$, $v = 5$ conviennent.
Vérification : $252 \times (-2) + 105 \times 5 = -504 + 525 = 21$ ✓
Théorème de Gauss. Si $a \mid bc$ et $\text{PGCD}(a,b) = 1$, alors $a \mid c$.
Attention ! Le théorème de Gauss exige que $a$ et $b$ soient premiers entre eux. Sans cette hypothèse, $a \mid bc$ n'implique pas $a \mid c$ (ex. : $4 \mid 2 \times 6$ mais $4 \nmid 6$).
6Congruences
Définition. Soient $a, b \in \mathbb{Z}$ et $n \in \mathbb{N}^*$. On dit que $a$ est congru à $b$ modulo $n$, et on note $a \equiv b \pmod{n}$, si $n \mid (a - b)$, c'est-à-dire si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
Exemples.- $17 \equiv 5 \pmod{6}$ car $6 \mid (17-5) = 12$.
- $-3 \equiv 4 \pmod{7}$ car $7 \mid (-3-4) = -7$.
Propriétés des congruences. Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors :
- $a + c \equiv b + d \pmod{n}$ (addition)
- $a - c \equiv b - d \pmod{n}$ (soustraction)
- $ac \equiv bd \pmod{n}$ (multiplication)
- $a^k \equiv b^k \pmod{n}$ pour tout $k \in \mathbb{N}$ (puissance)
Calcul de reste de puissance. Calculons $3^{100} \pmod{7}$ :
- $3^1 \equiv 3$, $3^2 \equiv 2$, $3^3 \equiv 6$, $3^4 \equiv 4$, $3^5 \equiv 5$, $3^6 \equiv 1 \pmod{7}$
- $100 = 6 \times 16 + 4$ donc $3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 4 \equiv 4 \pmod{7}$
Les puissances de 3 modulo 7 forment un cycle de longueur 6 (ordre de 3 dans ℤ/7ℤ).
Attention ! On ne peut pas simplifier $ka \equiv kb \pmod{n}$ en $a \equiv b \pmod{n}$ que si $\text{PGCD}(k,n) = 1$. En général, $ka \equiv kb \pmod{n} \implies a \equiv b \pmod{n/d}$ où $d = \text{PGCD}(k,n)$.
7Applications : cryptographie et calendriers
L'arithmétique modulaire trouve des applications concrètes en informatique, cryptographie et vie quotidienne.
Critères de divisibilité. Un entier $n$ écrit en base 10 est divisible par :
- $2$ si son chiffre des unités est pair ;
- $3$ si la somme de ses chiffres est divisible par $3$ ;
- $9$ si la somme de ses chiffres est divisible par $9$ ;
- $11$ si la somme alternée de ses chiffres est divisible par $11$.
Code ISBN-10 (contrôle d'erreur). Un code ISBN-10 $d_1 d_2 \ldots d_{10}$ est valide si $$\sum_{i=1}^{10} i \cdot d_i \equiv 0 \pmod{11}.$$ Cela permet de détecter une erreur sur un chiffre.
Exemple (calendrier). Si aujourd'hui est un lundi (jour 1), quel jour sera-t-il dans $100$ jours ?
- $100 = 7 \times 14 + 2$, donc $100 \equiv 2 \pmod{7}$.
- Jour $1 + 2 = 3$ → mercredi.
Chiffrement de César. Pour chiffrer une lettre de rang $x \in \{0,\ldots,25\}$ avec clé $k$ : $$x \mapsto (x + k) \pmod{26}.$$ Pour déchiffrer : $y \mapsto (y - k) \pmod{26}$.
★À retenir
À retenir — Arithmétique :
• Division euclidienne : $a = bq + r$, $0 \leq r < |b|$.
• Algorithme d'Euclide : $\text{PGCD}(a,b) = \text{PGCD}(b, r)$ — itérer jusqu'à $r = 0$.
• Bézout : il existe $u, v \in \mathbb{Z}$ tels que $au + bv = \text{PGCD}(a,b)$.
• Gauss : $a \mid bc$ et $a \wedge b = 1 \Rightarrow a \mid c$.
• Congruences : $a \equiv b \pmod{n} \iff n \mid (a-b)$ — stables par +, −, ×.
• Nombres premiers : tout entier $\geq 2$ se décompose de façon unique en produit de premiers.