Морозов Владимир Владимирович,
учитель математики и информатики
НОУ частной школы "Ступени", Москва.

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

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

Мы убеждёны в плодотворности и перспективности подобных занятий, ибо именно на стыке наук рождаются открытия!

В этой работе мы будем рассматривать решение нелинейного диофантова уравнения вида axy+bx+cy=d, где a, b, c, d – целые числа, и решение отыскивается также среди целых чисел.

Если a=0, то уравнение принимает вид bx+cy=d; решение этого классического уравнения подробно описано в литературе, программа его решения на компьютере опубликована http://morozko1967.narod.ru/soft.htm.

Пусть a0. Тогда уравнение

axy+bx+cy=d (1)

можно записать в виде

y(ax+c)+bx=d (2).

Зададим себе вопрос: может ли ax+c быть равным нулю? Да, если c делится на a и x= –c/a. Тогда решение существует, если bx=d, иными словами, bc+ad=0. Итак, мы получили такой вывод: если bc+ad=0 и c делится на а, то существует решение:

x= –c/a, y – любое целое число.

Точно также, если b делится на а, то существует решение

x – любое число, y= –b/a. Если bc+ad=0, но ни с, ни b не делятся на а, то решений нет.

Пусть теперь bc+ad0. Тогда нет целого х, обращающего в 0 выражение (ax+c). В этом случае уравнение можно записать в виде

Докажем, что уравнение (3) имеет конечное число целочисленных решений. Рассмотрим функцию

Естественно, эта функция является биекцией. Графиком функции является гипербола.

Заметим, что

Значит, при достаточно больших значениях переменной х значение переменной y близко к

Между какими целыми числами заключено это число?

Начиная с некоторого значения переменной х переменная y, стремясь к

и остаётся дробной. Точно также, если отрицательное х велико по модулю, то переменная y, стремясь к

и остаётся дробной. Следовательно, уравнение (3) имеет конечное число целочисленных решений, и их можно поручить отыскать компьютеру простым перебором.

Но для этого необходимо найти отрезок на оси абсцисс, вне которого гарантированно нет целочисленных решений уравнения (3).

Если b не делится на а, то, очевидно, что границы целочисленных х равны

Если b делится на а, то границы целочисленных х равны

Рассмотрим эти два случая отдельно.

Случай 1. Пусть сначала b не делится на а. Найдём

Обозначим

Числа

и y=B удовлетворяют уравнению (1). Поэтому

Далее нам потребуется…

Лемма. Пусть a, b – целые, отличные от нуля. Тогда

Если b не делится на а, то

Доказательство.

Сначала докажем, что для любого нецелого х

[–x]+1=–[x]. (5)

Действительно, по определению целой и дробной частей

x=[x]+{x}, –x=[–x]+{–x};

{–x}=1–{x},

[–x]+1= – x–{–x}= –x–1+{x}=–x–(1-{x})= –x–{–x}=[–x].

Итак, [–x]= –[x]–1.

Допустим противное, пусть

Возможны два случая: b делится на а, и b не делится на а. Если b не делится на а, то из (5) получаем

то есть b делится на а, что невозможно.

Если же b делится на а, то

По условию а отлично от нуля. Полученное противоречие доказывает, что

Докажем теперь второе неравенство леммы. Пусть b не делится на а. Допустим противное,

Тогда

Но это означает, что b делится на a. Полученное противоречие доказывает, что если b не делится на а, то

Лемма доказана.

Доказанная лемма позволяет из соотношения (4) найти

и в случае, если b не делится на а

Обозначим

Тогда все целочисленные решения уравнения (3) удовлетворяют оценке

AxD,

и уравнение (3) можно решить простым перебором, беря по очереди целые значения х от А до D, вычисляя соответствующие

и проверяя, является ли найденное значение у целым. Если d–bx делится на ax+c, то существует решение

Случай 2. Пусть b делится на а. Тогда границы целочисленных х равны

Найдём сначала

Обозначим

Тогда F удовлетворяет соотношению

Учитывая, что в этом случае b делится на а, получаем:

Теперь найдём

Обозначим

Тогда G удовлетворяет соотношению

Учитывая, что в этом случае b делится на а, получаем:

Обозначим

Тогда все целочисленные решения уравнения (3) удовлетворяют оценке

MxN,

и уравнение (3) можно решить простым перебором, беря по очереди целые значения х от А до D, вычисляя соответствующие

и проверяя, является ли найденное значение у целым. Если d–bx делится на ax+c, то существует решение

Итак, оба случая рассмотрены, осталось написать программу для персонального компьютера.

Исходный код программы на языке Pascal можно посмотреть в <Приложениии 1>, а также мы разместили его здесь: http://guopolysaevo.narod.ru/arc/sdiof17.zip.