Алгоритм Корначчи

Алгоритм Корначчи — это алгоритм решения диофантова уравнения $x^{2}+dy^{2}=m$ , где $1\leq d<m$ , а d и m взаимно просты. Алгоритм описал в 1908 Джузеппе Корначчи^[1].

Алгоритм

Сначала находим любое решение $r_{0}^{2}\equiv -d{\pmod {m}}$ . Если такого $r_{0}$ не существует, исходное уравнение не имеет примитивных решений. Без потери общности можно считать, что $r_{0}\leq {\tfrac {m}{2}}$ (если это не так, заменим r₀ на m - r₀, которое остаётся корнем из -d). Теперь используем алгоритм Евклида для поиска $r_{1}\equiv m{\pmod {r_{0}}}$ , $r_{2}\equiv r_{0}{\pmod {r_{1}}}$ и так далее. Останавливаемся, когда $r_{k}<{\sqrt {m}}$ . Если $s={\sqrt {\tfrac {m-r_{k}^{2}}{d}}}$ является целым числом, то решением будет $x=r_{k},y=s$ . В противном случае примитивного решения нет.

Для поиска непримитивных решений (x, y), где НОД(x, y) = g ≠ 1, заметим, из существования такого решения следует, что g² делит m (и, эквивалентно, что если m является свободным от квадратов, то все решения примитивны). Тогда вышеприведённый алгоритм можно использовать для поиска примитивного решения (u, v) уравнения $u^{2}+dv^{2}={\tfrac {m}{g^{2}}}$ . Если такое решение найдено, то (gu, gv) будет решением исходного уравнения.

Пример

Решаем уравнение $x^{2}+6y^{2}=103$ . Квадратный корень из −6 (mod 103) равен 32 и 103 ≡ 7 (mod 32). Поскольку $7^{2}<103$ и ${\sqrt {\tfrac {103-7^{2}}{6}}}=3$ , существует решение x = 7, y = 3.

Примечания

↑ Cornacchia, 1908, с. 33–90.

Литература

G. Cornacchia. Su di un metodo per la risoluzione in numeri interi dell' equazione $\sum _{h=0}^{n}C_{h}x^{n-h}y^{h}=P$ . // Giornale di Matematiche di Battaglini. — 1908. — Т. 46.