Теория делимости в кольце целых чисел

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:20, 17 мая 2016.

Рассмотрим кольцо целых чисел.

TemplateDifinitionIcon.svg Определение «Определение - Делимость »
( делит ), если
- делитель, - кратное.
TemplateDifinitionIcon.svg Определение «Определение - Отношение делимости»
Отношение делимости - бинарное отношение на кольце целых чисел : т.е. подмножество декартова произведения:
множество пар.

Свойства делимости

Основные теоремы и определения

и представление неоднозначно. Например: для того, чтобы представление было однозначным:
TemplateLemmaIcon.svg Лемма «О делимости с остатком»
и


Все, рассмотренное выше, справедливо для колец целостности (где нет делителей нуля).

TemplateLemmaIcon.svg Лемма «Теорема»
- целостное кольцо, , старший коэффициент обратим в


Все, что будет рассмотрено далее, верно для Евклидовых колец.

TemplateDifinitionIcon.svg Определение «Определение - Евклидово кольцо»
Евклидово кольцо :

Наибольший общий делитель (GСD)

TemplateDifinitionIcon.svg Определение «Определение - Общий делитель чисел»
- общий делитель чисел , если
TemplateDifinitionIcon.svg Определение «Определение - Наибольший общий делитель чисел»
Наибольшим общим делителем чисел (НОД ()) называется число , если:
  1. - общий делитель чисел ;

Базовые утверждения

TemplateTheoremIcon.svg Теорема Утверждение
Существует число, которое
  1. является общим делителем чисел ;
  2. делится на все другие делители.

То есть, существует единственный НОД.

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

Рассмотрим множество линейных комбинаций этих чисел.

Пусть - наименьшее по модулю из чисел . Покажем, что является НОД.

  1. Покажем, что . Если общий делитель, следовательно, делится на , то есть,
  2. Пусть то есть, не делит , , т.е. - линейная комбинация , (с точностью до знака)


TemplateLemmaIcon.svg Лемма «Утверждение»
Пусть - разбиение. Если , то


TemplateLemmaIcon.svg Лемма «Утверждение»


Алгоритм Евклида

Задача. Найти . Решается с помощью Алгоритма Евклида

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое  — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.

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

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

  • Пусть , тогда НОД (a,b) = НОД (b,r).
    1. Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда  ; где и — целые числа из определения.
    2. Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а (выражение в скобках есть целое число, следовательно, k делит r без остатка)
    3. Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
    4. Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
    5. В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
  • для любого ненулевого .
TemplateTheoremIcon.svg Теорема Утверждение
В алгоритме Евклида выполняется соотношение
Доказательство
  • Если ;
  • Если


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

Бинарный метод нахождения НОД

Бинарный метод нахождения НОД (Бинарный алгоритм Евклида) — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Он основан на использовании следующих свойств НОД:

Алгоритм

  1. Если чётные, то
  2. Если чётное, нечётное, то
  3. Если чётное, нечётное, то
  4. Если нечётные, то

Матричное представление НОД

(остатки записываются в виде рекуррентного соотношение второго порядка). Эту последовательность можно представить в виде регистра сдвига с нелинейной обратной связью.
Ri Ri+j.png

Состояние регистра обозначим через вектор

если применяем матрицу много раз. Матрицы обратимы.

Тогда получим

Расширенный алгоритм Евклида

Вход: - положительные целые числа

Выход

Метод

Диофантовы уравнения

TemplateDifinitionIcon.svg Определение «Определение -Диофантово уравнение»
- диофантово уравнение в целых числах.
TemplateTheoremIcon.svg Теорема Утверждение
разрешимо, то есть,
Доказательство

Необходимость

- решение уравнения , то есть, - линейная комбинация этих чисел.

Поэтому

Достаточность

Пусть (коэффициенты можно найти по алгоритму Евклида).

найдено новое решение, уравнение разрешимо.


TemplateTheoremIcon.svg Теорема Утверждение
Пусть .
- решение диофантова уравнения . Тогда множество решений этого уравнения совпадает с:
Доказательство

Пусть - решение

______________________

- целые, т.к.
- решение.