Линейное диофантово уравнение, часть 1

Вот задача, взятая без каких-то модификаций из сборника для подготовки к ЕГЭ:

Найти наименьшее натуральное число, кратное 23, которое при делении на 17 даёт в остатке 12.

Задача смешная, буквально анекдотическая. Первым натуральным числом, кратным 23, является само 23, и остаток от его деления на 17 равен 6. Следующее такое число — это 46, и для него остаток… равен тому самому 12. Что тут решать-то? Желание проверить первые несколько подходящих чисел вполне естественно, и если уже второе из них удовлетворяет условию… Тут даже не хочется думать и оптимизировать: а зачем?

А вот другая задача на эту же тему:

Найти наименьшее натуральное число, кратное 77, которое при делении на 74 даёт в остатке 48.

Это уже немного интереснее. Искомое число, кратное 77, очевидно, имеет вид \(77n\). При \(n=1\) получаем \(77=3\mod 74\). При \(n=2\) имеем \(77\times2=154=6\mod74\). Вообще, поскольку \(77=74+3\), при каждом увеличении \(n\) на единицу остаток от деления \(77n\) на \(74\) увеличивается на три. А сколько раз нужно взять по три, чтобы набрать требуемое 48? Очевидно, 16 раз. Это и даёт ответ на поставленный вопрос: искомое число равно \(16\times77=1232\).

Однако не всегда всё получается так гладко. Переставим в первой задаче два числа местами:

Найти наименьшее натуральное число, кратное 17, которое при делении на 23 даёт в остатке 12.

Ищем число \(17n\), такое что \(17n=12\mod23\). При \(n=1\) имеем \(17=17\mod23\), при \(n=2\) получаем \(17\times2=34=11\mod23\), далее \(17\times3=51=5\mod23\) и т.д. Прежний метод не работает: остаток «скачет». (На самом деле воспользоваться тем методом таки можно, но об этом в следующий раз!)

Решение задачи, как нетрудно видеть, сводится к уравнению

$$
17n=23m+12,\tag{1}
$$

причём \(n,m\) должны быть натуральными. Это линейное диофантово уравнение. Теоретически профильный вариант школьной программы по математике предполагает знакомство с такими уравнениями… но, увы, именно что теоретически.

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

$$
17n-23m=12
$$

$$
17n-17m-6m=12
$$

$$
17(n-m)-6m=12
$$

$$
(2\times6+5)(n-m)-6m=12
$$

$$
6(2n-2m)+5(n-m)-6m=12
$$

$$
6(2n-3m)+5(n-m)=12
$$

$$
5(3n-4m)+(2n-3m)=12
$$

Уравнение свелось к виду, в котором один из коэффициентов оказался равным единице; так всегда можно сделать. Представим число 12 в виде \(5\times2+2=12\), откуда \(3n-4m=2\) и \(2n-3m=2\). Эта система без труда решается школьными методами: \(n=m=-2\). Соответственно, \(17n=-34\).

Но это число отрицательное, а по условию задачи требуется натуральное! Ничего страшного: посмотрим на уравнение (1) внимательнее и заметим, что добавление к обеим частям числа, кратного одновременно 17 и 23, сохраняет равенство. Поскольку наименьшее общее кратное 17 и 23 равно 391, под условие задачи подходят все числа вида \(391k-34\). Из них наименьшим положительным является \(391-34=357\), это и есть ответ на вопрос задачи.