ах = c(mod Ь). (1")
То же самое можно выразить словами: "ах сравнимо с с по модулю b" или "ах принадлежит тому же классу вычетов по модулю Ь, что и с". Т. е. мы свели уравнение с двумя неизвестными (х и у) к уравнению с одним неизвестным, поскольку ясно, что из (1'), зная х, сразу же можно найти у. Однако х все же не произволен, а именно — удовлетворяет (1").
Кроме того, можно усмотреть следующее. Уравнение (1') (или (1")) — это неоднородное сравнение первой степени (т. е. линейное сравнение). Согласно общей теории, общее решение неоднородного сравнения есть сумма частного решения неоднородного сравнения и общего решения однородного сравнения ах = ()(mod b). Таким образом, задача разбилась на две.
Займемся сначала неоднородным сравнением (1") — Рассматривая эквивалентное уравнение (1'), замечаем (стандартное рассуждение — см. [1]), что если числа а и b делятся на число k, то на это же число должно делиться и с. Поскольку это верно для любого общего делителя а и Ь, то это верно и для их наибольшего общего делителя (а, Ь) =< 1. Таким образом, делимость с на <1 — необходимое условие разрешимости сравнения (1").
В нашем случае а = 27, b = 8, (а, Ь) = 1, т. е. числа а и b взаимно просты, поэтому сравнение (1") разрешимо при любом с.
Из приведенного рассуждения следует и способ решения сравнения (1") — Если мы умеем решить уравнение ах0 — by0 =< d, то умножив его на целое число c/d (поскольку необходимо с делится на d), мы получим решение уравнения (1').
В нашем случае d = 1, и кратчайший способ решения уравнения ах0 — by0 = 1 дается в [2]. Именно, надо разложить число a/b в цепную дробь, и если а = рn, b = qn то положить х = (-1)n-1qn-1, y = (-1)n-1pn-1.Это следует просто из того, что qn_1pn — qnpn-1 = (-1)n-1.
В нашем случае
Поэтому
И в самом деле: 27∙3–8∙10 = 81–80 = 1, поэтому берем x0 = 3, у0 = 10. Значит частным решением уравнения аx1 — by1 = с будет х1 =3∙2, y1 = 10∙2.
Что касается однородного уравнения ах — by = 0, то очевидным семейством решений его будет х = b∙k, у = a∙k, k — произвольное целое число. То, что это общее решение однородного уравнения следует из того, что данное уравнение эквивалентно сравнению ах = ()(mod b) и в силу взаимной простоты а и b это сравнение можно поделить на а (см. [3]), после чего сравнение превращается в х = ()(mod b), т. е. х должно делиться на Ь.
В итоге, получаем решение
уравнения (1). Поэтому в исходных переменных получаем:
Если здесь положить k = —1, то получаем дираковское решение: n0 = n3 = —2. Однако видно, что оно вовсе не наименьшее, и существует множество других, еще меньше. Впрочем, в каком-то смысле дираковский ответ действительно наименьший из возможных: именно, если искать наименьшее по абсолютной величине возможное количество рыб, то таким в самом деле окажется (-2).
Список литературы
[1] Энциклопедия элементарной математики. Государственное изд-во технико-теоретической лит-ры. М.-Л., 1951, стр. 285.
[2] Энциклопедия элементарной математики. Государственное изд-во технико-теоретической лит-ры. М.-Л., 1951, стр. 303.
[3] Энциклопедия элементарной математики. Государственное изд-во технико-теоретической лит-ры. М.-Л., 1951, стр. 275–276.
Рассмотрим вопрос о количестве решений уравнения