L’algorithme de Cornacchia

Abderrahmane Nitaj

We give in a simple way a new proof of the validity of Cornacchia’s algorithm. This algorithm consists of finding all primitive solutions (x, y) (if any) of the diophantine equation ax^{2} + by^{2} = m, where a, b and m are positive coprime integers. Our proof is based on some properties of the rational continued fractions.

1. Introduction

Soient a, b et m des entiers strictement positifs, premiers entre eux deux à deux et tels que m > a + b. On considère l’équation:

(1)  ax^{2} + by^{2} = m,

en entiers x ≠ 0 et y > 0. Une solution (x, y) de l’équation (1) vérifiant (x, y) = 1 sera appelée solution primitive. Puisque a, b et m sont premiers entre eux deux à deux, toute solution primitive vérifie: (ax, by) = (x, m) = (y, m) = 1. Si a = b = 1, on exige de plus que |x| > y > 0. On considère de même la congruence:

(2)  t^{2} ≡ −ba^{−1} (mod m),

avec 0 < t < m.

Dans cet article, nous donnons une nouvelle démonstration de l’algorithme de Cornacchia, qui date de 1908 (voir [1]) et qui permet de déterminer les solutions primitives de l’équation (1). Cette démonstration se distingue particulièrement par sa simplicité de celles qui ont été données récemment dans [2] et [4]. Voici une description de l’algorithme de Cornacchia.

Algorithme 1. (Cornacchia)

• Résoudre la congruence (2);

• Pour chaque solution t avec m/2 < t < m, appliquer l’algorithme d’Euclide à t et m; • Déterminer le premier reste r < \sqrt{m/a};

• Si \sqrt{(m − ar^{2})/b} est entier, alors (r, \sqrt{(m − ar^{2})/b}) est une solution de (1).

Nous verrons dans la partie 4 que toute solution obtenue par cet algorithme est primitive.

Notre démonstration de la validité de l’algorithme de Cornacchia se base sur l’utilisation de certaines propriétés du développement des nombres réels en fractions continues. Nous résumons ces outils dans la section 2. Dans la section 3, nous décrivons la résolution de l’équation (1), dans la section 4 nous donnons la nouvelle démonstration de l’algorithme de Cornacchia et dans la section 5, nous donnons une nouvelle version de cet algorithme, illustré par un exemple.

2. Les fractions continues

La fraction continue d’un nombre réel ξ ≠ 0 s’obtient de la façon suivante. On écrit:

ξ = a_{0} + \frac{1}{ξ_{1}} ,

où a_{0} = ⌊ξ⌋ est la partie entière de ξ. On recommence ensuite en remplaçant dans l’expression ci-dessus ξ par ξ_{1}, ce qui donne un entier a_{1} et un réel ξ_{2}. Par ce procédé, on obtient les formules de récurrence:

ξ_{i} = a_{i} + \frac{1}{ξ_{i+1}} , i ≥ 0,

avec ξ_{0} = ξ et a_{i} = ⌊ξ_{i}⌋. On a alors l’expression:

ξ = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \frac{1}{...}}}} ,

et on écrit tout simplement ξ = [a_{0}, a_{1}, a_{2}, a_{3}, …], qu’on appelle développement de ξ en fraction continue. Si ξ est rationnel, son développement en fraction continue est fini. En adoptant la convention que le dernier terme, s’il existe, est strictement supérieur à 1, alors le développement en fraction continue de tout réel est unique. Pour i ≥ 0, les réduites u_{i}/v_{i} de ξ sont obtenues en prenant (u_{i}, v_{i}) = 1 et

\frac{u_{i}}{v_{i}} = [a_{0}, …, a_{i}].

Si on convient que u_{−2} = 0, v_{−2} = 1, u_{−1} = 1, v_{−1} = 0, alors on a les relations de récurrence, valables pour tout i ≥ 0:

\begin{matrix}u_{i} = a_{i}u_{i−1} + u_{i−2}, \\ v_{i} = a_{i}v_{i−1} + v_{i−2}. \end{matrix}

Parmi les propriétés des fractions continues, nous aurons besoin des résultats suivants:

Théorème 1. ([3], p. 10) Soit ξ un nombre réel non nul. Soient u_{n}/v_{n} et u_{n+1}/v_{n+1} deux réduites consécutives de ξ. Pour tout couple (a, b) d’entiers, si 0 < b < v_{n+1}, alors |bξ − a| ≥ |v_{n}ξ − u_{n}|.

Théorème 2. ([3], p. 11) Soit ξ un nombre réel. Si la fraction irréductible a/b avec b ≥ 1 vérifie:

|ξ − \frac{a}{b}| < \frac{1}{2b^{2}} ,

alors a/b est une réduite de la fraction continue de ξ.

Théorème 3. ([3], p. 8, 9) Soit ξ un nombre réel non nul et soient u_{i}/v_{i}, i ≥ −2 ses réduites (si ξ est rationnel, le nombre s de ses réduites est fini). Alors

0 < v_{0} ≤ v_{1} < v_{2} < ⋯,

et pour tout i ≥ 1 (i ≤ s si ξ est rationnel):

|v_{i}ξ − u_{i}| > |v_{i+1}ξ − u_{i+1}|.

3. Résolution de l’équation (1)

La résolution de l’équation (1) en entiers x et y est basée sur le théorème suivant.

Théorème 4. Soit (x, y) une solution de l’équation (1) vérifiant x ≠ 0, y > 0 et (x, y) = 1. Alors il existe une solution t de (2) et une réduite u/v de t/m telles que x = tv − mu et y = v.

Preuve. Soit (x, y) une solution de l’équation (1) avec (x, y) = 1. Alors (y, m) = 1 et on peut définir t par t ≡ xy^{−1} (mod m) et 0 < t < m. Ainsi t est une solution de la congruence (2) et il existe un entier u tel que x = ty −mu. L’hypothèse a+b < m implique |x|y ≠ 1 et donc 0 < 2|x|y < x^{2} + y^{2} ≤ ax^{2} + by^{2} = m. Alors:

|\frac{u}{y} − \frac{t}{m}| = \frac{|x|}{my} < \frac{1}{2y^{2}} .

Le théorème 2 montre alors que u/y est une réduite de t/m. ■

Le théorème 4 montre comment déterminer certaines solutions de l’équation (1) en résolvant la congruence (2) et en calculant les réduites des différents rationnels t/m. La proposition suivante montre que toutes les solutions obtenues de cette façon sont primitives.

Proposition 1. Soit t une solution de la congruence (2). Si (x, y) est une solution de (1) vérifiant x ≡ ty (mod m), alors (x, y) est primitive.

Preuve. Si t est une solution de la congruence (2), alors il existe un entier q tel que at^{2} + b = mq. Si x et y vérifient x ≡ ty (mod m), alors il existe un entier u tel que x = ty −mu, et donc ax^{2} +by^{2} = m (qy^{2} − 2atuy + mau^{2}). Si (x, y) vérifie ax^{2} +by^{2} = m, alors

qy^{2} − 2atuy + mau^{2} = (qy − 2atu)y + mau^{2} = 1

et donc (m, y) = 1, ce qui montre que (x, y) est primitive. ■ La proposition suivante montre qu’une solution t de la congruence (2) donne au plus une solution primitive pour l’équation (1), et donc que le nombre de solutions primitives de cette équation est au plus égal au nombre de solutions de la congruence (2).

Proposition 2. Soit t une solution de la congruence (2). Si (x, y) et (x′, y′) sont deux solutions primitives de l’équation (1) vérifiant x ≡ ty (mod m) et x′ ≡ ty′ (mod m), alors x = x′ et y = y′.

Preuve. Des congruences x ≡ ty (mod m) et x′ ≡ ty′ (mod m), on tire:

axx′ + byy′ ≡ (at^{2} + b)yy′ ≡ 0 (mod m),

et donc axx′ + byy′ = mq_{1} où q_{1} est entier. On a aussi xy′ − yx′ ≡ 0 (mod m) et donc xy′ − yx′ = mq_{2} où q_{2} est entier. Des égalités ax^{2} + by^{2} = m et ax^{′2} + by^{′2} = m, on tire:

(axx′ + byy′)^{2} + ab(xy′ − yx′)^{2} = m^{2},

ce qui donne:

(3)  q_{1}^{2} + abq_{2}^{2} = 1.

Supposons d’abord que a = b = 1. Les solutions vérifient par hypothèse 0 < y < |x| et 0 < y′ < |x′|. Si dans (3) on a q_{1} = 0, alors xx′ + yy′ = 0 et donc puisque (x, y) = 1 et (x′, y′) = 1, alors x = ±y′ et y = ∓x′. L’inégalité 0 < y < |x| donne 0 < |x′| < y′ ce qui est impossible. Alors on a q_{2} = 0 dans (3), d’où x/y = x′/y′, ce qui donne x = x′ et y = y′. Supposons maintenant que ab > 1. La relation (3) implique alors que q_{2} = 0, et comme ci-dessus, on a x = x′ et y = y′. ■

4. L’algorithme de Cornacchia

Nous dirons qu’une solution t de la congruence (2) produit une solution (x, y) pour l’équation (1) s’il existe une réduite u/v de t/m telle que x = tv − mu et y = v. Nous donnons dans cette partie la démonstration de l’algorithme de Cornacchia. Contrairement au théorème 4, cet algorithme ne permet de déterminer que les solutions positives de l’équation (1). D’autre part, l’algorithme de Cornacchia ne considère que les solutions t de la congruence (2) vérifiant m/2 < t < m. En fait, nous avons la proposition suivante.

Proposition 3. Soit t une solution de la congruence (2) avec 0 < t < m/2. Si (x, y) est une solution de de (1) produite par t, alors (−x, y) est une solution de (1) produite par m − t.

Preuve. Développons t/m en fraction continue, t/m = [a_{0}, a_{1}, a_{2}, …, a_{s}] avec a_{s} ≥ 2, a_{0} = ⌊t/m⌋ = 0 et a_{1} = ⌊m/t⌋ ≥ 2. Alors ([3], p. 15)

(m − t)/m = 1 − t/m = [0, 1, a_{1} − 1, a_{2}, a_{3}, …, a_{s}].

Soient u_{i}/v_{i} et u′_{i}/v′_{i}, i ≥ −2 les réduites de t/m et (m − t)/m respectivement. On montre facilement par récurrence que pour tout 1 ≤ i ≤ s, u′_{i} = v_{i−1} − u_{i−1} et v′_{i} = v_{i−1}. Si (x, y) est une solution produite par t, alors x = ty − mu où u/y est une réduite de t/m. Alors (y − u)/y est une réduite de (m − t)/m et

(m − t)y − m(y − u) = −(ty − mu) = −x

et donc (−x, y) est une solution produite par m − t. ■ Maintenant, on peut se limiter aux solutions t de la congruence (2) vérifiant m/2 < t < m. Nous allons établir le lien entre la suite des restes considérés dans l’algorithme 1 et la suite des entiers x = tv − mu, où u/v est une réduite de t/m, considérés dans le théorème 4. Soit t une solution de la congruence (2) avec m/2 < t < m. La suite des restes considérés dans l’algorithme 1 est obtenue en appliquant l’algorithme d’Euclide à t et m. On définit les suites (a_{i}) et (r_{i}) par:

\begin{aligned}t & = a_{0}m + r_{0}, \\ m & = a_{1}r_{0} + r_{1}, \\ r_{i−1} & = a_{i+1}r_{i} + r_{i+1}, (i = 1, …, s − 1). \end{aligned}

Nous avons en particulier a_{0} = 0, a_{1} = 1, r_{0} = t, r_{s} = 0, et pour tout 1 ≤ i ≤ s, a_{i} ≥ 1 et r_{i} < r_{i−1}. La fraction continue de t/m est (voir [5], p. 325):

t/m = [0, 1, a_{2}, …, a_{s}].

Proposition 4. Soient u_{i}/v_{i}, (−2 ≤ i ≤ s) les réduites de t/m. Pour tout 0 ≤ i ≤ s, x_{i} = tv_{i} − mu_{i} = (−1)^{i}r_{i}.

Preuve. Pour i = 0 on a x_{0} = tv_{0} − mu_{0} = t = r_{0}. Pour i = 1, on a x_{1} = tv_{1} − mu_{1} = t − m = −r_{1}. Supposons que l’égalité ait lieu jusqu’au rang i. Alors:

tv_{i+1} − mu_{i+1} = t(a_{i+1}v_{i} + v_{i−1}) − m(a_{i+1}u_{i} + u_{i−1})
= a_{i+1}(tv_{i} − mu_{i}) + tv_{i−1} − mu_{i−1}
= (−1)^{i}a_{i+1}r_{i} + (−1)^{i−1}r_{i−1}
= (−1)^{i+1}(r_{i−1} − a_{i+1}r_{i})
= (−1)^{i+1}r_{i+1}.

Ceci montre donc la proposition. ■ La proposition ci-dessus montre que les solutions obtenues par l’algorithme de Cornacchia sont primitives. Nous donnons maintenant la démonstration de cet algorithme.

Théorème 5. Soit t une solution de la congruence (2) avec m/2 < t < m. Soient u_{i}/v_{i}, i ≥ −2 les réduites de t/m, x_{i} = tv_{i} − mu_{i} et y_{i} = v_{i}. Si t produit une solution (x_{k}, y_{k}) pour l’équation (1), alors k est le plus petit entier i ≥ 0 tel que |x_{i}| < \sqrt{m/a}.

Preuve. Si une solution t de la congruence (2) produit une solution (x_{k}, y_{k}) pour l’équation (1), d’après le théorème 4, elle est de la forme x_{k} = tv_{k} − mu_{k}, y_{k} = v_{k} où u_{k}/v_{k} est une réduite de t/m, avec k ≥ 0. Puisque ax_{k}^{2} + by_{k}^{2} = m et x_{k}y_{k} ≠ 0, alors:

|x_{k}| < \sqrt{m/a}  et  y_{k} < \sqrt{m/b}.

Soit i_{0} ≥ 0 le plus petit entier tel que |x_{i_{0}}| < \sqrt{m/a}. Si i_{0} < k, alors (théorème 3) y_{i_{0}} ≤ y_{k} < \sqrt{m/b} et donc ax_{i_{0}}^{2} + by_{i_{0}}^{2} < 2m. D’autre part,

0 < ax_{i_{0}}^{2} + by_{i_{0}}^{2} = a(tv_{i_{0}} − mu_{i_{0}})^{2} + bv_{i_{0}}^{2} ≡ 0 (mod m),

alors ax_{i_{0}}^{2} + by_{i_{0}}^{2} = m et donc (x_{i_{0}}, y_{i_{0}}) est aussi une solution de l’équation (1) produite par t, ce qui contredit la proposition 1. ■

5. Nouvelle version de l’algorithme et exemple

Nous donnons maintenant un algorithme basé sur l’utilisation des fractions continues pour déterminer toutes les solutions primitives de l’équation (1). Si on connait la factorisation de m, plusieurs méthodes permettent de résoudre la congruence (2) (voir [2] et [5]).

Algorithme 2. (ax^{2} + by^{2} = m)

Entrée: a > 0, b > 0, m > a + b, premiers entre eux deux à deux.

Initialisation: Déterminer les solutions t_{j}, j = 1, …, n_{0} de t^{2} ≡ −ba^{−1} (mod m) telles que m/2 < t_{j} < m;

j := 0;
Tant que j ≤ n_{0} − 1 répéter
j := j + 1;
y_{−1} := 0;
i := −1;
Tant que y_{i} < \sqrt{m/b} répéter
i := i + 1;
Calculer la réduite \frac{u_{i}}{y_{i}} de \frac{t_{j}}{m};
x_{i} := t_{j}y_{i} − mu_{i};
Si |x_{i}| < \sqrt{m/a} et y_{i} < \sqrt{m/b}alors écrire x_{i} et y_{i}.

Exemple. Pour illustrer l’algorithme 2, nous avons traité l’exemple suivant avec l’aide de Maple. Soient a = 317, b = 15 et

m = 1938758870912466947228 = 2^{2} · 239 · 55286879 · 36681225047.

La première étape de l’algorithme 2 consiste à résoudre la congruence at^{2}+b ≡ 0 (mod m), avec m/2 < t < m. On trouve les valeurs suivantes:

t_{1} = 1540268285466516237559, t_{2} = 1624103215407503974869,
t_{3} = 1352352495007639360927, t_{4} = 1812019005866380851501,
t_{5} = 1096119300502319569341, t_{6} = 1555785811361061059915,
t_{7} = 1284035090961196445973, t_{8} = 1367870020902184183283.

La deuxième étape consiste à déterminer pour chaque t_{j}, 1 ≤ j ≤ 8, l’unique réduite (s’il en existe) u/y de t_{j}/m qui vérifie les inégalités y < \sqrt{m/b} et |t_{j}y − mu| < \sqrt{m/a}. La table ci-dessus résume cette recherche.

\begin{matrix}t_{j} & u & y & x \\ t_{1} & − & − & − \\ t_{2} & − & − & − \\ t_{3} & − & − & − \\ t_{4} & − & − & − \\ t_{5} & − & − & − \\ t_{6} & 9082110491 & 11317767621 & −234156733 \\ t_{7} & 7520168509 & 11354668973 & 123452677 \\ t_{8} & − & − & − \end{matrix}

Ainsi les seules solutions primitives sont les huit couples

(x, y) = (±234156733, ±11317767621), (±123452677, ±11354668973).

Remarque. On peut obtenir toutes les solutions de l’équations (1) (y compris les solutions non primitives) en résolvant les différentes équations ax_{d}^{2} + by_{d}^{2} = m/d^{2} où d^{2} décrit l’ensemble des diviseurs carrés de m. Les solutions de (1) sont alors de la forme (dx_{d}, dy_{d}).

Références

[1] G. Cornacchia, Su di un metodo per la risoluzione in numeri interi dell’ equazione ∑_{h=0}^{n} C_{h}x^{n−h}y^{h} = P, Giornale di Matematiche di Battaglini 46 (1908), 33−90.

[2] K. Hardy, J. B. Muskat, and K. S. Williams, A deterministic algorithm for solving n = fu^{2} + gv^{2} in coprime integers u and v, Math. Comp. 55 (1990), 327 − 343.

[3] S. Lang, Introduction to Diophantine Approximations, Addison-Wesley Publishing Compagny, Reading, Massachusetts, 1966 [4] F. Morain, Courbes elliptiques et tests de primalité, Thèse (1990), Université

de Lyon 1.

[5] I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, John Wiley and Sons, (New York) 1991.

Département de Mathématiques Université de Caen, 14032, Caen Cedex France (e-mail nitaj@math.unicaen.fr)