Algorithme de Cornacchia

Soit donc l'équation ${\displaystyle x^{2}+dy^{2}=m}$, où ${\displaystyle 1\leq d<m}$, et les entiers ${\displaystyle d}$ et ${\displaystyle m}$ sont premiers entre eux. On suppose ${\displaystyle (x,y)}$ également premiers entre eux.

On obtient d'abord ${\displaystyle x_{0}}$ tel que ${\displaystyle x_{0}^{2}=-d{\bmod {m}}}$, en utilisant n'importe quelle méthode de calcul de racines carrées modulaires. Si ${\displaystyle -d}$ n'est pas un résidu quadratique modulo ${\displaystyle m}$, l'équation de départ n'a pas de solution. Puis on déploie l'algorithme d'Euclide étendu sur la paire ${\displaystyle (x_{0},m)}$, ce qui donne la séquence suivante :

$${\displaystyle {\begin{aligned}x_{0}&=a_{0}m+r_{0}\\m&=a_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{i}&=a_{i+2}r_{i+1}+r_{i+2}\end{aligned}}}$$

On arrête lorsque l'on atteint un rang ${\displaystyle k}$ tel que ${\displaystyle r_{k}^{2}<m<r_{k-1}^{2}}$. Si ${\displaystyle m-r_{k}^{2}\neq 0{\bmod {d}}}$, l'équation de départ n'a pas de solution. Dans le cas contraire, on vérifie que ${\displaystyle (m-r_{k}^{2})/d}$ est un carré. Si ce n'est pas le cas, l'équation de départ n'a pas de solution. Sinon, on conclut en exhibant une solution

$${\displaystyle x=r_{k},y={\sqrt {\frac {m-u^{2}}{d}}}.}$$

Les solutions de ce type sont dites primitives. Si maintenant on ne suppose plus ${\displaystyle (x,y)}$ premiers entre eux, alors ${\displaystyle \gcd(x,y)^{2}|m}$ ! en particulier, si ${\displaystyle m}$ est sans carrés, toutes les solutions de l'équation sont primitives. Sinon, on note ${\displaystyle g}$ tel que ${\displaystyle g^{2}|m}$ et on résout l'équation ${\displaystyle x'^{2}+dy'^{2}=m'}$ avec ${\displaystyle m'=m/g^{2}}$. Une solution non-primitive est alors obtenue en prenant ${\displaystyle (x,y)=(gx',gy')}$.

La description de Cornacchia ne contenait pas de preuve que cet algorithme est correct. Il a fallu pour cela attendre la fin du 20^e siècle, et plusieurs preuves très différentes ont depuis été proposées[7] - [8] - [9], dont un argument élégant de François Morain par réduction au problème de Thue[10]. L'algorithme de Cornacchia s'étend aisément à des anneaux plus larges que ${\displaystyle \mathbb {Z} }$, notamment l'anneau ${\displaystyle \mathbb {Z} [i]}$ des entiers de Gauss[11].