Строение идеалов полукольца натуральных чисел (стр. 4 из 5)

Теорема 9. Пусть

, Обозначим

, ,…,

Тогда

.

Доказательство. База метода математической индукции для значений k=2,3 доказана в теоремах 7 и 8. Предположив, что выполняется

, доказательство проводится аналогично доказательству теоремы 8.

Предложение. В

порожденном идеале выполняется .

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

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

Крайний случай доказанного выше отношения позволяет найти элемент

.

Теорема 10.

.

Доказательство. Заметим, что образующие образуют полную систему вычетов по модулю

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

, то

Теорема 11. Если

‒ наименьший образующий -порожденного идеала , то , причем обе оценки точные.

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

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

С другой стороны,

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

и

.

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

Действия программы:

1. Сортирует введенные образующие в порядке возрастания (процедура Sort).

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

3. Выводит линейно независимую систему образующих, находит их НОД (процедура NOD). Если НОД

1, то осуществляется деление каждой образующей на НОД, дальнейшая работа происходит с новой системой.

4. Проверяет элементы полукольца

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

Библиографический список

1. Абрамов А.М. Квант, №3, 1984. с. 40-41.

2. Атья М., Макдональд И. Введение в коммутативную алгебру [Текст] / М. Атья, И. Макдональд. – М.:Мир,1972.

3. Вечтомов Е.М. Введение в полукольца [Текст] / Е.М. Вечтомов. – Киров: Изд-во ВГПУ, 2000.

4. Коганов Л.М. О функциях Мебиуса и константах Фробениуса полугрупп, порожденных линейными формами специального вида / Межвузовский сборник научных трудов Полугруппы и частичные группоиды, Ленинград, 1987. с. 15-25.

5. Скорняков, Л.А. Элементы теории структур [Текст]/Л.А. Скорняков.– М.: Наука, 1982.

6. Чермных, В.В. Полукольца [Текст]/В.В. Чермных. – Киров: Изд-во ВГПУ, 1997.

Приложение 1.

Примеры работы программы при различных исходных данных.

Приложение 2.

Описание алгоритма работы программы "FindC" с помощью блок-схем.

Приложение 3

Полный текст программы "FindC".

unit SearchFirstElementSequence;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Edit: TEdit;

Button1: TButton;

Memo: TListBox;

Button2: TButton;

procedure EditKeyUp(Sender: TObject; var Key: Word; Shift: TShiftState);

procedure Button2Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);