Arithmétique — Mathématiques

§ 1 Divisibilité dans $\mathbb{Z}$

Définition

$a$ divise $b$, noté $a \mid b$, s'il existe $k\in\mathbb{Z}$ tel que $b = ka$. Propriétés : transitivité, stabilité par combinaison linéaire, antisymétrie sur $\mathbb{N}^*$.

Division euclidienne

$\forall a\in\mathbb{Z},\ b\in\mathbb{Z}^*$, $\exists! (q,r)\in\mathbb{Z}\times\mathbb{N}$ tel que :

$$a = bq + r, \quad 0 \leq r < |b|.$$

Existence : $q = \lfloor a/b\rfloor$, $r = a-bq$. Unicité : si $bq+r = bq'+r'$ alors $b(q-q')=r'-r$ avec $|r'-r|<|b|$, donc $q=q'$ et $r=r'$. □

§ 2 PGCD et algorithme d'Euclide

Définition — PGCD, PPCM

$\pgcd(a,b)$ : plus grand commun diviseur positif de $a$ et $b$.
$\mathrm{ppcm}(a,b)$ : plus petit commun multiple positif.

$$\pgcd(a,b) \times \mathrm{ppcm}(a,b) = |ab|$$

Algorithme d'Euclide

$a = bq + r,\ r\neq 0 \Rightarrow \pgcd(a,b) = \pgcd(b,r)$. On itère jusqu'à $r = 0$ ; le dernier reste non nul est $\pgcd(a,b)$.

Exemple — $\pgcd(252,\, 105)$

$252 = 2\times 105 + 42$
$105 = 2\times 42 + 21$
$42 = 2\times 21 + 0$

Donc $\pgcd(252, 105) = 21$.

§ 3 Identité de Bézout

Théorème de Bézout

$\exists u,v\in\mathbb{Z}$ tels que $au + bv = \pgcd(a,b)$. L'ensemble $\{au+bv\mid u,v\in\mathbb{Z}\}$ est exactement $\pgcd(a,b)\cdot\mathbb{Z}$.

$I = \{au+bv\}$ est un idéal de $\mathbb{Z}$, donc $I = d\mathbb{Z}$. $d$ divise $a$ et $b$ (par division euclidienne), donc $d \leq \pgcd(a,b)$. Mais $\pgcd(a,b)\in I$, d'où $d = \pgcd(a,b)$. □

Lemme de Gauss

Si $a \mid bc$ et $\pgcd(a,b)=1$, alors $a \mid c$.

Par Bézout, $au+bv=1$, donc $acu+bcv=c$. Comme $a\mid acu$ et $a\mid bc$ donne $a\mid bcv$, on conclut $a\mid c$. □

§ 4 Nombres premiers

Théorème fondamental de l'arithmétique

Tout entier $n\geq 2$ se décompose de façon unique en produit de premiers :

$$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$

Infinité des premiers (Euclide)

Il existe une infinité de nombres premiers.

Si $p_1,\ldots,p_k$ sont tous les premiers, posons $N = p_1\cdots p_k+1$. Un facteur premier $p$ de $N$ n'est aucun $p_i$ (il ne divise pas $1$). Contradiction. □

Théorème des nombres premiers (1896)

$$\pi(x) \;\sim\; \frac{x}{\ln x} \quad (x\to+\infty)$$

où $\pi(x)$ désigne le nombre de premiers $\leq x$.

§ 5 Congruences

Définition

$a \equiv b \pmod{n}$ si $n \mid (a-b)$. Relation d'équivalence compatible avec $+$ et $\times$.

Petit théorème de Fermat

Si $p$ est premier et $\pgcd(a,p)=1$ :

$$a^{p-1} \equiv 1 \pmod{p}$$

Les éléments $a, 2a, \ldots, (p-1)a$ sont distincts mod $p$. Leur produit $(p-1)!\,a^{p-1} \equiv (p-1)!\pmod{p}$, et en simplifiant par $(p-1)!$ : $a^{p-1}\equiv 1$. □

Condition	Solutions de $ax\equiv b\pmod{n}$
$d\nmid b$, $d=\pgcd(a,n)$	Aucune
$d\mid b$, $d=1$	Une unique classe mod $n$
$d\mid b$, $d>1$	$d$ classes mod $n$

§ 6 Théorème chinois des restes

Théorème — Sunzi (~IIIe siècle)

Si $n_1,\ldots,n_k$ sont deux à deux premiers entre eux, le système :

$$x \equiv a_i \pmod{n_i},\quad i=1,\ldots,k$$

admet une solution unique modulo $N = n_1\cdots n_k$.

Posons $N_i = N/n_i$, $M_i = N_i^{-1}\bmod n_i$ (inversible car $\pgcd(N_i,n_i)=1$). La solution est $x = \sum a_i N_i M_i \pmod N$. □

§ 7 Indicatrice d'Euler

Définition

$\varphi(n) = |\{k\in\{1,\ldots,n\} : \pgcd(k,n)=1\}|$.

$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

$n$	$\varphi(n)$	Remarque
$p$ premier	$p-1$
$p^k$	$p^{k-1}(p-1)$
$pq$	$(p-1)(q-1)$	Base de RSA

Théorème d'Euler

Si $\pgcd(a,n)=1$ :

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

§ 8 Application : RSA

Génération des clés

Choisir deux grands premiers $p$, $q$ distincts.
$n = pq$, $\lambda(n) = \mathrm{ppcm}(p-1, q-1)$.
Choisir $e$ avec $\pgcd(e, \lambda(n))=1$.
$d = e^{-1} \pmod{\lambda(n)}$.
Clé publique $(n,e)$ · Clé privée $d$.

Chiffrement

$$c = m^e \bmod n$$

Déchiffrement

$$m = c^d \bmod n$$

Correction

$ed\equiv 1\pmod{\lambda(n)}$ (par construction), donc par Euler : $c^d = m^{ed} \equiv m \pmod{n}$.

Sécurité

Repose sur la difficulté de factoriser $n=pq$. L'algorithme de Shor (quantique) factoriserait $n$ en temps polynomial.