WikiDer > Алгоритм Корнаккиаса - Википедия

В вычислительная теория чисел, Алгоритм корнаккии является алгоритм для решения Диофантово уравнение ${ displaystyle x ^ {2} + dy ^ {2} = m}$, куда ${ Displaystyle 1 Leq d <м}$ и d и м находятся совмещать. Алгоритм был описан в 1908 году Джузеппе Корнаккиа.^[1]

Алгоритм

Во-первых, найдите решение ${ Displaystyle r_ {0} ^ {2} Equiv -d { pmod {m}}}$ (возможно, используя алгоритм, указанный здесь); если нет такого ${ displaystyle r_ {0}}$ существуют, примитивного решения исходного уравнения быть не может. Без ограничения общности можно считать, что р₀ ≤ м/2 (если нет, то замените р₀ с м - р₀, который по-прежнему будет корнем -d). Затем используйте Евклидов алгоритм найти ${ Displaystyle r_ {1} эквив м { pmod {r_ {0}}}}$, ${ Displaystyle R_ {2} Equiv R_ {0} { pmod {r_ {1}}}}$ и так далее; остановись, когда ${ displaystyle r_ {k} <{ sqrt {m}}}$. Если ${ displaystyle s = { sqrt { tfrac {m-r_ {k} ^ {2}} {d}}}}$ является целым числом, то решение ${ displaystyle x = r_ {k}, y = s}$; в противном случае попробуйте другой корень -d пока не будет найдено решение или пока не будут исчерпаны все корни. В этом случае примитивного решения нет.

Чтобы найти непримитивные решения (Икс, у) куда gcd (Икс, у) = грамм ≠ 1, заметим, что из существования такого решения следует, что грамм² разделяет м (и эквивалентно, что если м является без квадратов, то все решения примитивны). Таким образом, описанный выше алгоритм может использоваться для поиска примитивного решения. (ты, v) к ты² + dv² = м/грамм². Если такое решение будет найдено, то (гу, gv) будет решением исходного уравнения.

Пример

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

Рекомендации

внешняя ссылка

• Базилла, Дж. М. (2004). "О решениях ${ displaystyle x ^ {2} + dy ^ {2} = m}$" (PDF). Proc. Japan Acad. 80 (А): 40–41.