3.8.6. Решение арифметических задач. Процедура PARI (D. Bourgoin, 1978)

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

Модуль I): произведение — константа. Этот модуль использует разложение числа на простые множители или делители, например:

Модуль конгруэнтность. Модуль делает заключения о простых равенствах, основываясь на разложениях небольших чисел (2, 3, 5, 7, 11), чисто комбинаторным способом. Этот модуль выводит необходимые условия, которым должны удовлетворять неизвестные величины, например

Модуль делимость. Этот модуль делает заключение о делимости, основываясь на фундаментальной лемме Гаусса: “Если а есть взаимно простое число с и делится на произведение то а делится на например

(Модуль 4): равенство. Этот модуль умеет находить частные решения простых уравнений путем последовательных испытаний (идеальным случаем здесь было бы использование непрерывных (цепных) дробей), например

(Модуль 5): обобщенное евклидово деление. Модуль рассчитывает частное и остаток от деления полинома на полином, например

Модуль 6): индукция. Этот модуль умеет находить, исходя из начального значения и рекуррентного отношения, формальное выражение для общего члена последовательности, например

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

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

Ниже приводятся три примера решений с использованием метода

Пример 1. Найти два простых числа и таких, что

Модуль “делимость” лучше всего соответствует заданным условиям. Он “считает”, что имеется уравнение относительно и формирует новое условие делимости:

Модуль «конгруэнтность» не дает здесь ничего нового уже известны как нечетные числа, так как они являются простыми числами). Но тот же модуль становится теперь наилучшим кандидатом для прямого исследования начального условия и конгруэнций по модулю 3, порождая выражение

Если по модулю 3, то являющееся простым числом, может быть только равным 3; отсюда следует

Получаем решение

Если по модулю 3, то конгруэнтное уравнение принимает вид

пусть (по модулю 3), т. е. (как простое число), тогда

но это противоречит предположению, что по модулю 3. Если по модулю 3, то получаем

пусть снова (по модулю 3) и, следовательно, тогда

что в данном случае удовлетворяет предположение по модулю 3.

Итак, задача имеет два решения: (3; 1) и (5; 3).

Пример 2. Найти целые положительные такие, что

Для заданной задачи наиболее пригоден модуль «евклидово деление», в результате применения которого получаем тождество

Трехчлен должен быть общим делителем обеих частей этого тождества и, следовательно, должен делить и «остаток» Модуль «делимость» формирует здесь новое условие:

к которому снова применяется модуль “евклидово деление” для получения нового тождества

Трехчлен должен снова делить обе части этого тождества, и, в частности

пусть где — целое число. Модуль “произведение = константа” играет здесь роль ключа для проверки значений Программа выполняет решение 12 уравнений второй степени, соответствующих этим 12 возможным значениям например

Множество решений в целом представляет собой набор чисел 0, 1, 2, 3, 5. Но это еще не есть заключение, получаемое программой, которая знает, что пока получена только последовательность эквивалентных значений, а не последовательность необходимых условий. Для получения последних необходимо проверить, удовлетворяет ли каждое полученное решение исходному выражению. При проверке отсекается решение и окончательными решениями задачи будут числа 0, 1, 2 и 5.

Пример 3. Найти все целые такие, что

Здесь используется модуль “индукция”. Вначале он проверяет условие задачи (I) для случая Затем он делает в условии (I) подстановку вместо чтобы попытаться доказать, что оно не теряет силу при переходе от Отдельно взятый общий член ряда условия (I) порядка будет иметь вид

Используя теперь (I) в качестве правила переписывания, получим

или, после сокращения в обеих частях этого равенства в силу того, что есть целое число, получаем тривиальное равенство

Таким образом, первоначальная теорема доказана по индукции.

Несколько задач, решенных программой PARI

1. Найти такие, что

2. Доказать тождества:

3. Пусть задана последовательность

Показать, что член этой последовательности может быть записан как

4. Решить относительно переменной следующую систему уравнений:

5. Для. каких значений х выражение делит без остатка выражение

6. Доказать конгруэнтность следующих выражений:

7. Показать что имеют одинаковые остатки при делении их на 7.

8. Найти значение х, такое, что

9. Доказать, что если есть взаимно простые числа, то число является составным.

10. Показать, что равенство имеет решения в числах взаимно простых с числом 2 и превосходящих его.

11. Определить все целые такие, что 6 чисел будут взаимно простыми.

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

ведет в поиске его ”интуиция“ или тот род знания высшего уровня, который позволяет ему одновременно и управлять своими поисками, и упрощать себе работу, опуская при поиске неинтересные детали. Иначе говоря, действия математика направляет некоторая метатеория.

Существуют программы, которые также эффективно используют метатеорию. Ниже описана первая среди них — программа Ж. Питра (1966 г.).