Целые решения линейного уравнения в границах

Точное число целых пар ax + by = c внутри заданных границ, параметрическое семейство и до ста показанных решений.

Ваш пример

Все поля — целые числа от −10¹² до 10¹². Границы включены; единицы количества задаются самой задачей.

Разбор примера

Подходящих пар: 2

Первые допустимые пары по выбранному параметру; не обязательно по возрастанию x
xy
22
50
  1. НОД(|a|,|b|)=3.
  2. Частное решение: x₀=-10, y₀=10.
  3. Все целые решения: x=-10+(3)t, y=10+(-2)t.
  4. Оставляем только целые t, удовлетворяющие обеим включённым границам.
Всего решений
2
Показано пар
2
Остальные
0

Метод и условия расчёта

Расширенный алгоритм Евклида даёт частное решение. Семейство x=x₀+(b/g)t, y=y₀−(a/g)t пересекается с целочисленными границами.

Вопросы по теме

Программа перебирает весь большой прямоугольник?

Нет. Число решений вычисляется по границам параметра; вывод ограничен ста парами.

Можно ввести нулевой коэффициент?

Да. Уравнение с одним нулём и случай a=b=0 рассматриваются отдельно; конечные границы обязательны.

Теория чисел: углубление: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.