Terminale · maths expertes

Fiche résumé : Arithmétique (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.

Divisibilité : $a \mid b \iff b = ka$ avec $k \in \mathbb{Z}$. Si $a \mid b$ et $a \mid c$, alors $a \mid bu + cv$ pour tous $u, v \in \mathbb{Z}$.
Division euclidienne : pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$, il existe un unique couple $(q, r)$ tel que $a = bq + r$ et $0 \leqslant r < b$.
Congruence : $a \equiv b \;[n] \iff n \mid a - b \iff$ même reste modulo $n$. Compatible avec $+$, $-$, $\times$ et les puissances. Pas de division en général.
Reste d'une puissance : trouver $m$ avec $a^m \equiv 1 \;[n]$, écrire $k = mq + s$, alors $a^k \equiv a^s \;[n]$.
PGCD : $\mathrm{PGCD}(a, b) = \mathrm{PGCD}(b, a - bq)$. Algorithme d'Euclide : le PGCD est le dernier reste non nul.
Identité de Bézout : il existe $u, v$ avec $au + bv = \mathrm{PGCD}(a,b)$. Coefficients obtenus en remontant l'algorithme d'Euclide.
Théorème de Bézout : $\mathrm{PGCD}(a,b) = 1 \iff$ il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$.
Théorème de Gauss : si $a \mid bc$ et $\mathrm{PGCD}(a, b) = 1$, alors $a \mid c$.
Corollaire : si $a \mid n$, $b \mid n$ et $\mathrm{PGCD}(a,b) = 1$, alors $ab \mid n$.
Inverse modulo $n$ : $a$ a un inverse modulo $n$ si et seulement si $\mathrm{PGCD}(a, n) = 1$.
Équation $ax + by = c$ : solutions si et seulement si $\mathrm{PGCD}(a,b) \mid c$. Méthode : solution particulière, soustraction, Gauss, réciproque. Si $\mathrm{PGCD}(a,b)=1$ et $(x_0, y_0)$ solution : $x = x_0 + bk$, $y = y_0 - ak$.
Nombres premiers : exactement deux diviseurs positifs. Tout $n \geqslant 2$ a un diviseur premier ; si $n$ est composé, il a un diviseur premier $p \leqslant \sqrt{n}$. Il y a une infinité de nombres premiers.
Lemme d'Euclide : $p$ premier et $p \mid ab \Rightarrow p \mid a$ ou $p \mid b$.
Décomposition : $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, unique ; nombre de diviseurs positifs $(\alpha_1 + 1) \cdots (\alpha_k + 1)$.
Petit théorème de Fermat : $p$ premier, $a^p \equiv a \;[p]$ ; si $p \nmid a$, $a^{p-1} \equiv 1 \;[p]$. Réciproque fausse.
Chiffrement affine : $y \equiv ax + b \;[26]$, valable si et seulement si $\mathrm{PGCD}(a, 26) = 1$ ; déchiffrement $x \equiv a'(y - b) \;[26]$ avec $aa' \equiv 1 \;[26]$.
RSA : $n = pq$, $ed \equiv 1 \;[(p-1)(q-1)]$, alors $m^{ed} \equiv m \;[n]$.