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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Алгоритм Корначчи — это алгоритм решения диофантова уравнения , где , а d и m взаимно просты. Алгоритм описал в 1908 Джузеппе Корначчи[1].

Алгоритм[править | править код]

Сначала находим любое решение . Если такого не существует, исходное уравнение не имеет примитивных решений. Без потери общности можно считать, что (если это не так, заменим r0 на m - r0, которое остаётся корнем из -d). Теперь используем алгоритм Евклида для поиска , и так далее. Останавливаемся, когда . Если является целым числом, то решением будет . В противном случае примитивного решения нет.

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

Пример[править | править код]

Решаем уравнение . Квадратный корень из −6 (mod 103) равен 32 и 103 ≡ 7 (mod 32). Поскольку и , существует решение x = 7, y = 3.

Примечания[править | править код]

  1. Cornacchia, 1908, с. 33–90.

Литература[править | править код]

  • G. Cornacchia. Su di un metodo per la risoluzione in numeri interi dell' equazione . // Giornale di Matematiche di Battaglini. — 1908. — Т. 46.

Ссылки[править | править код]

Basilla, Julius Magalona On Cornacchia's algorithm for solving the diophantine equation (PDF) (12 May 2004).