Deux entiers a et b, deux coefficients entiers u et v, et une égalité qui décide de tout : au + bv = pgcd(a, b).
Énoncée ainsi, la relation de Bézout ressemble à une curiosité d'arithmétique. Elle est en réalité le pivot de toute la théorie des nombres premiers : c'est elle qui donne un sens à « premiers entre eux », elle qui démontre que si un nombre premier divise un produit il divise l'un des facteurs, elle qui fait de ℤ/pℤ un corps où tout élément non nul s'inverse — et elle, enfin, qui fabrique la clé privée de RSA. Cette page la construit, puis la met au travail.
Faites courir u et v sur tous les entiers : les valeurs obtenues ne remplissent pas la droite, elles s'espacent régulièrement. La droite ax + by = c ne rencontre le réseau que si c est bien choisi.
L'ensemble des au + bv est exactement l'ensemble des multiples du pgcd : ni plus, ni moins. Plus grand est le pgcd, plus les droites sont écartées et plus il est difficile de tomber sur un point du réseau. Le cas où tout devient possible dès c = 1 est celui où le pgcd vaut 1 — autrement dit celui où a et b sont premiers entre eux.
À gauche, l'algorithme d'Euclide tel que les Grecs le voyaient : on pave un rectangle avec les plus grands carrés possibles. À droite, le même calcul avec deux colonnes en plus, qui suivent les coefficients au fil des divisions.
Le pavage s'arrête quand un carré tombe juste : son côté est le pgcd, et c'est la plus grande longueur qui mesure exactement les deux côtés. Les colonnes u et v suivent la même récurrence que les restes — chaque reste s'écrit dès le départ comme une combinaison de a et de b, si bien que la dernière ligne est la relation de Bézout, sans qu'on ait rien à remonter.
Placez b jetons en cercle et sautez de a en a. Vous ne visitez pas forcément tout le monde : vous ne visitez que les multiples du pgcd. Et si vous atteignez le jeton n° 1, le nombre de sauts qu'il a fallu est exactement le coefficient u de Bézout.
Atteindre le jeton 1 signifie qu'il existe u avec a·u ≡ 1 (mod b), c'est-à-dire a·u + b·v = 1 : la relation de Bézout et l'inversibilité modulo b sont la même chose écrite deux fois. Et cela n'arrive que si a et b sont premiers entre eux. Réglez b sur un nombre premier : quel que soit a non multiple de b, la ronde passe partout.
La table de multiplication modulo n dit tout. Modulo un nombre premier, aucune case du corps n'est nulle en dehors de la première ligne et de la première colonne : chaque ligne est une permutation, donc chaque élément a un inverse.
Le lemme d'Euclide — si un nombre premier p divise un produit ab, alors il divise a ou il divise b — se démontre en une ligne avec Bézout : si p ne divise pas a, alors pgcd(p, a) = 1, donc il existe u et v avec pu + av = 1 ; en multipliant par b on obtient b = pub + (ab)v, et comme p divise les deux termes de droite, p divise b. Retirez l'hypothèse « premier » et tout s'effondre : la lecture ci-dessus affiche, pour chaque n composé, un contre-exemple explicite. C'est ce lemme, et lui seul, qui rend unique la décomposition en facteurs premiers.
Une fois admise, la relation de Bézout gouverne des choses très éloignées de l'arithmétique élémentaire : une densité, un pire cas, et la sécurité de vos communications.
Un point du réseau est visible depuis l'origine si et seulement si ses deux coordonnées sont premières entre elles — sinon un point plus proche le masque exactement. Or la proportion de couples premiers entre eux vaut 6/π² ≈ 0,6079, parce que la probabilité qu'aucun premier p ne divise les deux vaut le produit des (1 − 1/p²), c'est-à-dire 1/ζ(2). Deux entiers tirés au hasard ont donc un peu moins de deux chances sur trois d'admettre une relation de Bézout égale à 1. La convergence est lente : l'écart décroît comme log N / N, ce qui se lit sur la courbe.
Le pire cas de l'algorithme d'Euclide, à taille donnée, est toujours un couple de Fibonacci consécutifs : ce sont les nombres dont tous les quotients valent 1, donc ceux qui font maigrir les restes le plus lentement possible. C'est le théorème de Lamé (1844), premier résultat de complexité de l'histoire. Il en découle que le calcul du pgcd — et donc des coefficients de Bézout — coûte un nombre de divisions proportionnel au nombre de chiffres, soit environ 4,785 divisions par décade. C'est cette lenteur de croissance qui rend le chiffrement à clé publique praticable.
La clé publique est le couple (n, e). Le déchiffrement demande un exposant d tel que e·d ≡ 1 (mod φ(n)) : c'est exactement l'inverse de e modulo φ(n), et il n'existe que parce que e et φ(n) sont premiers entre eux — Bézout le fournit en une poignée de divisions. Qui connaît p et q calcule φ(n), donc d, donc lit le message. Qui ne connaît que n doit d'abord factoriser : toute la sécurité tient dans cet écart de difficulté, entre un algorithme d'Euclide instantané et une factorisation hors de portée.