Курсовая работа (т): Китайская Теорема об остатках и её следствия

Таким образом, среди рассматриваемых чисел найдётся число , которое при делении на даёт остаток . В то же время при делении на число N даёт остатки соответственно.

Наиболее используемая формулировка КТО:

Пусть - попарно взаимно простые числа и - произвольные целые числа. Тогда существует целое число ,такое что Целое число у удовлетворяет условию  тогда и только тогда когда

Доказательство: Обозначим М=и . Тогда числа  являются взаимно простыми для всех i. Cледовательно существует целое число такое что  где . Положимтогда , поскольку числа . Аналогично доказывается, что . Пусть - остаток от деления числа a на M. Тогда и ≡ a (mod M). В частности  Далее, пусть целое чисто у удовлетворяет условию . Тогда т. е. Число делится на каждое из чисел .В силу того, что числа попарно взаимно простые, получаем что делится на число . Таким образом, ≡0 (mod ).Теорема доказана.

2. Примеры. Применение к решению олимпиадных задач

В этом параграфе я опишу один из методов решения систем линейных сравнений. Это очень древний алгоритм. Он применялся еще в античности для решения проблем астрономии. Приведу несколько примеров решения олимпиадных задач и примеров решения сравнений с помощью КТО. Начнем с задачи, сформулированной на современном языке, которая могла бы рассматриваться древними астрономами (Астрономический пример).

Пример 1: Три спутника пересекут меридиан города Лидса сегодня ночью: первый - в 1 ночи, второй - в 4 утра, а третий - в 8 утра. У каждого спутника свой период обращения. Первому на полный оборот вокруг Земли требуется 13 часов, второму - 15, а третьему - 19 часов. Сколько часов пройдет (от полуночи) до того момента, когда спутники одновременно пересекут меридиан Лидса?

Посмотрим, как эта задача переводится на язык сравнений.

Пусть х - количество часов, которые пройдут с 12 часов ночи до момента одновременного прохождения спутниками над меридианом Лидса. Первый спутник пересекает этот меридиан каждые 13 часов, начиная с часу ночи. Это можно записать

как х = 1 + 13t для некоторого целого t. Другими словами, х ≡ 1 (mod 13). Соответствующие уравнения для остальных спутников имеют вид: х ≡ 4 (mod 15) и х≡ 8 (mod 19). Таким образом, три спутника одновременно пересекут меридиан Лидса через х часов, если х удовлетворяет эти трем уравнениям. Следовательно, для ответа на поставленный вопрос достаточно решить систему сравнений:

х ≡ 1 (mod 13),

х ≡4 (mod 15), (B1)

х ≡ 8 (mod 19).

Заметим, что мы не можем складывать или вычитать уравнения системы, поскольку модули сравнений в них разные. Будем решать эту задачу, переходя от сравнений к уравнениям в целых числах. Так, сравнение х ≡ 1 (mod 13) соответствует диофантову уравнению: х = 1 + 13t. Заменяя х во втором сравнении системы на 1 + 13t, получаем:

+ 13t ≡ 4 (mod 15), т.е. 13t ≡ 3 (mod 15).

Но 13 обратимо по модулю 15, обратный к нему элемент - это 7. Умножая последнее сравнение на 7 и переходя в нем к вычетам по модулю 15, имеем:

t ≡ 6 (mod 15).

Значит, t может быть записан в виде: t = 6+15u для какого-то целого u. Следовательно,

х = 1 + 13t = 1 + 13(6 + 15u) = 79 + 195u.Заметим, что все числа вида 79 + 195u являются целыми решениями первых двух сравнений системы (B.1). Наконец, подставим в третье сравнение вместо х выражение 79 + 195u:

+ 195u ≡ 8 (mod 19), так что 5u ≡ 5 (mod 19).

Ввиду обратимости остатка 5 по модулю 19, на него можно сократить и увидеть, что

u ≡ 1 (mod 19). Переписывая это сравнение как диофантово уравнение, мы получим

u= 1 + 19v для некоторого целого v.

Итак, х = 79 + 195u = 79 + 195(1 + 19v) = 274 + 3705v.

Какой отсюда можно сделать вывод относительно спутников? Напомним, что х - количество часов, которые пройдут от полуночи до момента одновременного прохождения спутников над меридианом Лидса. Поэтому нам нужно было найти наименьшее натуральное значение переменной х, удовлетворяющее системе (B.1). Мы это сделали. Поскольку решение системы: х = 274 + 3705v, то ответ: 274. Итак, спутники одновременно пройдут над меридианом Лидса через 274 часа после 0 часов сегодняшней ночи, что соответствует 11 дням и 10 часам. Но общее решение системы дает больше информации. Прибавляя к 274 любое кратное 3705, мы получаем другое решение системы. Иначе говоря, спутники одновременно пересекают означенный меридиан каждые 3705 часов после первого такого момента, что соответствует 154 дням и 9 часам.

Пример 2: Найти все целые решения системы сравнений:

Решение: М= 3*5*7=105

Найдем целые числа ,,такие что :

1)*35≡1 (mod 3)  *2≡1 (mod 3)

=-1(mod 3)

)*21≡1 (mod 5)  *1≡1 (mod 5)

=1

)*15≡1 (mod 7)

=1

По КТО:

подставим найденные нами значения в формулу:

≡-1*35*2+ 1*21*3+1*15*2=23, т. е.

Числа вида 23+105t, где ,исчерпывают все множество решений исходной системы сравнений.

Ответ: 23+105t.

Пример 3: Доказать что сравнение ≡ 0 (mod m)разрешимо для каждого натурально числа m>1, несмотря на то, что уравнение =0 не имеет целых решений.

Поскольку =(2x+1)(3x+1), то уравнение не имеет решений в кольце . Пусть m=(2b+1). тогда по китайской теореме об остатках существует целое число х, такое, что 3х≡ -1(mod) и 2х≡-1(mod(2b+1)). Следовательно ≡0 (mod m).

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

Рассмотрим арифметическую прогрессию b,b+a,b+2a,…, где a,bN, Пусть ,,..., - простые числа, причем a<<<...<. По Китайской теореме об остатках существует натуральное число, такое,что a≡-b-aj (mod ), где j=1,2,…,m. Это означает, что числа b+a(+1), b+a(+2), b+a(+m) являются составными.

Пример 5: Доказать что для любых натуральных чисел ,таких что )=)=…=(=1, уравнение   имеет бесконечно много натуральных решений. Если n=1,то , - решение уравнения = при любом z.Если n>2, то по китайской теореме об остатках существует бесконечно много таких чисел z, что z (mod ), z(mod ). Для каждого такого z числа

,…,,

являются решениями нашего уравнения.

3. КТО. Применение к открытию сейфа в банке

Бенджамен Франклин (Franklin) однажды сказал: «Трое могут хранить тайну, если двое из них мертвы». В этом параграфе мы изучаем безопасную систему допуска живых к секретным сведениям, основанную на китайской теореме об остатках. Представьте себе следующую ситуацию

Пусть -попарно взаимно простые числа, такие, что .Пусть S- произвольное целое число с условием M<S<N и - остатки от деления S на .

Предположим, далее, что в некотором банке работают n кассиров. Кассир с номером i знает пару чисел .Для открытия сейфа необходимо знать ключевое число S. Докажем, что любые k кассиров смогут открыть сейф, но никакие (k-1) кассиров не смогут это сделать. Действительно, пусть собрались кассиры с номерами , тогда им известен набор чисел По КТО можно найти такое число , что . Так как, то a=S (ввиду единственности решения этой системы сравнений по модулю) и ключевое число найдено, т.е. сейф можно открыть. Если собрались (k-1) кассиров, то они знают пары чисел. По КТО они могут найти такое целое число b, что и , т. е. b≠S. Таким образом, b не является искомым ключом к открытию сейфа.

В качестве конкретного примера можно рассмотреть числа : и,например, S=4001. Каждый из пяти кассиров знает одну из пар чисел (5,9), (1.10), (32,49), (32,53),(48,59).

Из предыдущего следует, что любые три кассира смогут найти ключ (равный S=4001) и открыть сейф, но никакие два не смогут этого сделать.

Заключение

В выше приведённой работе была сформулирована китайская теорема об остатках, приведены её доказательства, а также указанно применение КТО к решению олимпиадных задач и к некоторым прикладным вопросам теории чисел.

Список литературы

1.      Бухштаб А.А. Теория чисел. - М: Просвящение,1996.

.        Кузьмина А.С., Мальцев Ю.А. Теория чисел: учебное пособие/ А.С. Кузьмина, Ю.Н. Мальцев. - Барнаул: АлтГПА,2011.-240с.

.        Коутинхо С. Введение в теорию чисел. Алгоритм RSA. Москва: Постчаркет, 2001. - 328 с.

.        Рыбников К.А. История математики: учебное пособие для университетов-Издательство Московского Университета,1960.