Code RSA

Commençons par supposer que $a$ et $b$ sont premiers entre eux.

L'ensemble $A = \{ax + by>0 \mid x, y \in \mathbb{Z} \}$ est non vide ($a+b > 0$), il contient donc un plus petit élément que l'on note $c=ax_0 + by_0$.

La division euclidienne de $a$ par $c$ donne : $a = qc+r$ avec $0 \leq r < c$. Comme $r = a-qc = a-q(ax_0 + by_0) = a(1-qx_0)+b(-qy_0)$ et que $r < c$, il ne peut être dans $A$. Ceci implique que $r=0$ et que $c$ divise $a$.

Le même raisonnement en utilisant la division euclidienne de $b$ par $c$ donne que $c$ divise $b$. Comme $a$ et $b$ sont premiers entre eux, $c$ ne peut valoir que 1.

Réciproquement, supposons qu'il existes deux entiers naturels $x$ et $y$ tels que $ax + by = 1$. Si $p$ est un diviseur commun à $a$ et $b$, on a $a=pa'$ et $b=pb"$ et donc $pa'x+pb'y = p(a'x+b'y) = 1$ ce qui implique que $p$ divise $1$ : $p = 1$.

Commençons par montrer qu'il existe une solution avec $x$ et $y$ positifs.

Comme $a$ est premier avec $b$ le théorème de Bézout indique qu'il existe deux entiers relatifs $x$ et $y$ tels que $ax + by = 1$, donc $ax = 1 + b(-y)$

De plus les entiers $a$ et $b$ étant positifs donc $x$ et $y$ sont de signe différents. Si $y>0$ il existe $k > 0$ tel que $ka > y$ et on a $ax + kab = 1 - by + kab$. L'égalité précédente donne $a(x + kb) = 1 + b(ka - y)$avec $x + kb$ et $ka - y$ positifs.

Continuons en montrant qu'il existe une solution telle que $0 \leq x < b$. On utilise pour cela la division euclidienne de $x$ par $b$ : $x = bq+r$ et $0\leq r < b$ ce qui donne $a(bq+r) = 1 + by$ et donc $ar = 1 + b(y-bq)$. Comme $r$ est positif, $ar$ l'est, donc $b(y-bq)$ aussi et $0\leq y-bq$ : il existe une solution telle que $x<b$.

Enfin, si $ax=1+by$ et $ax'=1+by'$ alors $a(x-x') = b(y-y')$ et comme $a$ et $b$ sont premiers entre eux $b$ divise $x-x'$. Il n'y a donc au plus qu'une seule solution telle que $x <b$.

Nous allons le faire par récurrence.

Si $a=1$, $a^{p}-a = 0$ qui est bien un multiple de $p$. On suppose la propriété vraie pour $a \geq 1$ et on s'intéresse à $a+1$ :

$$ (a+1)^{p}-(a+1) = \sum_{i=0}^pC_p^ia^i1^{p-i} -(a+1) = 1 + \sum_{i=1}^{p-1}C_p^ia^i + a^p -(a+1) = \sum_{i=1}^{p-1}C_p^ia^i + (a^p-a) $$

Comme par hypothèse de récurrence $p$ divise $(a^p-a)$, il nous reste à prouver que $p$ divise $\sum_{i=1}^{p-1}C_p^ia^i$. Nous allons le faire en montrant que $p$ divise $C_p^i$ pour tout $0 < i <p$. En effet :

$$ C_p^i = \frac{p!}{i!(p-i)!} = p \frac{(p-1)!}{i!(p-i)!} = p \frac{\Pi_{j=1}^{p-i+1}(p-j)}{i!} $$

Et comme $p$ ne peut diviser aucun $j$ pour tout $0 < j < p$ on en conclut que comme il est de plus premier, il ne peut pas non plus diviser $\Pi_{1\leq j \leq i}j = i!$ Ceci prouve que puisque $C_p^i$ est un entier, la quantité $\frac{\Pi_{j=1}^{p-i+1}(p-j)}{i!}$ est entière : $p$ divise $C_p^i$ pour tout $0 < i <p$.

$p$ divise bien $(a+1)^{p}-(a+1)$ s'il divise $a^{p}-a$, ce qui conclut la preuve par récurrence.