Skip to content

Диофантово уравнение

В математике диофантово уравнение представляет собой полиномиальное уравнение с двумя или более неизвестными и целочисленными коэффициентами, для которого интерес представляют только целочисленные решения.

Линейное диофантово уравнение можно описать как равенство константе суммы двух или более одночленов, каждый из которых имеет первую степень. Экспоненциальное диофантово уравнение — это уравнение, в котором неизвестные могут появляться в показателях степени.

Диофантовы задачи отличаются от уравнений тем, что количество уравнений меньше, чем неизвестных. В таких задачах необходимо найти целые числа, которые одновременно удовлетворяют всем уравнениям. Эти системы уравнений определяют алгебраические кривые, поверхности или более общие алгебраические множества, и их изучение составляет часть алгебраической геометрии, известную как диофантова геометрия.

Диофантовы уравнения применяются в современных криптографических алгоритмах. Например:

  1. Алгоритмы на основе эллиптических кривых (ECC), которые используются для шифрования и создания цифровых подписей.
  2. Задачи дискретного логарифмирования и факторизации, которые лежат в основе многих криптосистем.

В компьютерных науках используются в задачах оптимизации и поиска целочисленных решений. А так же в экономике и финансах в задачах оптимизации, где требуется найти целочисленные решения (например, распределение ресурсов).

Описание

Простейшее линейное диофантово уравнение имеет вид

\[ ax+by=c, \]

Доказательство: Если \(d\) - этот наибольший общий делитель, то соотношение Безу утверждает существование целых чисел \(e\) и \(f\), таких, что \(ae + bf = d\). Если c кратно \(d\), то \(c = dh\) для некоторого целого числа \(h\), и \((eh, fh)\) является решением. С другой стороны, для каждой пары целых чисел \(x\) и \(y\) наибольший общий делитель \(d\) из \(a\) и \(b\) делит \(ax + by\) на. Таким образом, если уравнение имеет решение, то c должно быть кратно \(d\). Если \(a = ud\) и \(b = vd\), то для каждого решения \((x, y)\) мы имеем

\[ \begin{align} a(x+kv) + b(y-ku) &= ax+by+k(av-bu) \\ &= ax+by+k(udv-vdu) \\ &= ax+by, \end{align} \]

показывающий, что \((x + kv, y − ku)\) является другим решением. И даны два таких решения, что

\[ ax_1 + by_1 = ax_2 + by_2 = c, \]

из этого можно сделать вывод, что

\[ u(x_2 - x_1) + v(y_2 - y_1) = 0. \]

Поскольку \(u\) и \(v\) взаимно просты, лемма Евклида показывает, что \(v\) делится на \(x2 − x1\), и, следовательно, существует целое число \(k\), такое, что оба

\[ x_2 - x_1 = kv, \quad y_2 - y_1 = -ku. \]

Следовательно,

\[ x_2 = x_1 + kv, \quad y_2 = y_1 - ku, \]

Реализация

python
from __future__ import annotations

from maths.greatest_common_divisor import greatest_common_divisor


def diophantine(a: int, b: int, c: int) -> tuple[float, float]:
    # (1)!
    assert (
        c % greatest_common_divisor(a, b) == 0
    )
    (d, x, y) = extended_gcd(a, b)
    r = c / d
    return (r * x, r * y)


def diophantine_all_soln(a: int, b: int, c: int, n: int = 2) -> None:
    # (2)!
    (x0, y0) = diophantine(a, b, c)
    d = greatest_common_divisor(a, b)
    p = a // d
    q = b // d

    for i in range(n):
        x = x0 + i * q
        y = y0 - i * p
        print(x, y)


def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    # (3)!
    assert a >= 0
    assert b >= 0

    if b == 0:
        d, x, y = a, 1, 0
    else:
        (d, p, q) = extended_gcd(b, a % b)
        x = q
        y = p - q * (a // b)

    assert a % d == 0
    assert b % d == 0
    assert d == a * x + b * y

    return (d, x, y)

  1. Если заданы три целых числа a, b и c, по крайней мере одно из которых не равно нулю, то диофантово уравнение ax + by = c будет иметь решение (где x и y — целые числа) в том случае, если наибольший общий делитель (gcd) чисел a и b делит число c.

  2. Lemma : if n|ab and gcd(a,n) = 1, то n|b

    Поиск всех решений диофантовых уравнений: Пусть gcd(a, b) = d, a = dp, b = dq. Если (x0, y0) — решение задачи Диофантова уравнения ax + by = c, то все решения можно представить в виде a(x0 + tq) + b(y0 – tp) = c, где t — произвольное целое число

    n - это нyжное вам решение, по умолчанию n = 2

  3. Расширенный алгоритм Евклида: если d является общим делителем чисел a и b и существует такое целое число x, что d = a * x + b * y, то d представляет собой наибольший общий делитель (НОД) чисел a и b