Китайська теорема про остачі

   Міністерство освіти і науки України

Національний педагогічний університет

імені М. П. Драгоманова

Фізико – математичний інститут

Кафедра вищої математики

КУРСОВА РОБОТА

з алгебри

на тему :

Китайська теорема про остачі

                                                  Автор: студентка 21 МІ групи

                                               Антонюк Олена Олександрівна

                     Науковий керівник :

              кандидат фізико-математичних наук,              

                     доцент Требенко О.О.

        Робота захищена : ”__”____2010р.

                      Оцінка _________________

                     Комісія :

                             1.______________________.

                             2.______________________.

                             3.______________________.

Київ-2010

Зміст

Вступ

Розділ 1. Історія розвитку питання...…………………………………………….4

Розділ 2. Система конгруенцій першого степеня

              2.1.Розв’язки системи конгруенцій………………………………………..5

2.2 Китайська теорема про остачі……………………………….………...6

2.3 Загальний розв’язок системи конгруенцій………….………………..7

Розділ 3. Приклади розв’язування задач…………………………………….…10

Висновки

Список використаної літератури

Вступ

Вступ

Актуальність дослідження полягає в тому,що «Китайська теорема про остачі» є одним з основних результатів елементарної теорії чисел. Широко застосовується в алгебрі й теорії чисел, молекулярній біології і медицині.

Метою курсової роботи було вивчити «Китайську теорему про остачі».

              Для реалізації мети було поставлено наступні завдання:

              1). Ознайомитись з поняттям системи лінійних конгруенцій та її розв’язку.

              2). Дослідити умови існування розв’язків.

              3). Розглянути способи розв’язування систем лінійних конгруенцій.

              Об’єктом дослідження є система лінійних конгруенцій.

              Предмет дослідження ─ китайська теорема про остачі.

              Робота складається із вступу, 3 розділів, висновків і списку використаної літератури. Обсяг роботи – 17 сторінок.

Розділ 1. Історія розвитку питання

Задачі, які зводяться до розгляду систем конгруенцій 1-го степеня, розглядаються  в арифметиці китайського математика Сун Цзу (Sun-Tsŭ), який жив приблизно на початку нашої ери. У нього, як у цілого ряду китайських, індуських, арабських і європейських вчених які розв’язували такі задачі після нього, ставили запитання в наступній формі: знайти число, яке дає дані остачі при діленні не наступне число. Тому твердження про еквівалентність системи конгруенцій за взаємно простим модулями і конгруенції за модулем добутку називають « китайською теоремою про остачі». Робота Сун Цзу стала відомою в Європі в 1852 році. Незалежно від китайських математиків спосіб розв’язування задач такого типу був поданий індуським математиком Брамегупта (588-660).

              Леонардо Фібоначчі в своїй книзі «Liber abaci» розглядав задачу знаходження числа, яке ділиться на 7 і має остачу 1 при діленні на 2, 3, 4, 5, 6.

              Нещодавно вченими із лабораторії Колд Спрінг Харбор було розроблено метод, який дозволяє одночасно визначити послідовність великої кількості ДНК. Швидкого визначення послідовності ДНК вимагають задачі сучасних молекулярної біології і медицини. Використовувана досі технологія дозволяла працювати одночасно лише із десятками зразків. Враховуючи високі темпи розвитку науки і складність досліджень, такої кількості дуже мало. Метод, розроблений вченими з Колд Спрінг Харбор, за їхніми словами, дозволить працювати одночасно із сотнями тисяч зразків. Цей метод (який одержав назву ДНК-судоку) ґрунтується на китайській теоремі про остачі. 

Розділ 2.Система конгруенцій першого степеня

              2.1.Розв’язки системи конгруенцій

              Обмежимося системою конгруенцій:

      (1)

з одним невідомим, але різними модулями.

              Розв’язати систему конгруенцій з одним невідомим – означає знайти такі цілі значення невідомого х, які задовольняли б усі конгруенції даної системи. Якщо за деяким модулем є розв’язком системи (1), то весь цей клас чисел прийматимемо за один розв’язок. Якщо дана система має хоч би один розв’язок, то вона називатиметься сумісною.

              Насамперед зауважимо, що, розв’язуючи окремо кожну з конгруенцій (1), матимемо систему, еквівалентну даній:

  (2)

              Отже, досить вміти розв’язувати систему конгруенцій (2).

              Неважко показати, що коли система (2) сумісна, то вона має єдиний розв’язок за модулем М, що дорівнює найменшому спільному кратному чисел

Справді, припустимо, що і - будь-які два розв’язки системи (2), тоді:

і

              Звідси , тобто різниця ділитиметься на число , отже, вона ділитиметься і на їх найменше спільне кратне .

              Таким чином, , а такі розв’язки ми не вважаємо різними.

              Розглянемо спочатку окремий випадок, коли модулі системи (2) попарно взаємно прості.

              2.2 Китайська теорема про остачі.

Теорема 1. Якщо модулі m1, m2, …, mk попарно взаємно прості, то система конгруенцій

матиме єдиний розв’язок:

(3)

де

причому числа Mi i yi визначаються з умов:

. (4)

Доведення.

              Справді, підставляючи значення в конгруенцію системи (2) і беручи до уваги, що всі , згідно з (4), діляться на і конгруенція має єдиний розв’язок щодо , бо , дістанемо :

тобто , визначене вказаним способом, задовольняє будь-яку конгруенцію системи (2), а тому і всю цю систему. Тим самим показано, що є єдиним розв’язком системи (2) за модулем , бо найменше спільне кратне попарно взаємно простих чисел дорівнює їх добутку.

Теорему доведено.

Приклад. Знайти число, яке при діленні на 17, 13 і 10 дає відповідно остачі 15, 11 і 3.

Позначимо шукане число через x, тоді задача зведеться до розв’язання такої системи конгруенцій:

Маємо

,

Розв’язуючи допоміжні конгруенції

дістанемо:

Отже, за теоремою,

буде розв’язком заданої системи конгруенцій. Звідси випливає, що найменшим натуральним числом, яке  задовольняє умову задачі, буде x=1103.

Відповідь:

              2.3 Загальний розв’язок системи конгруенцій.

В загально випадку коли модулі m1, m2, …, mk можуть і не бути попарно взаємно простими, систему (2) можна розв’язати так.

              З першої конгруенції системи (2) виходитиме, що всі значення x, яку його задовольняють, матимуть форму , де пробігає всі цілі числа. Щоб вибрати з них значення x , які б задовольняли й другу конгруенцію, визначимо з умови, що

або

Ця конгруенція першого степеня відносно t1 матиме розв’язки, якщо  ділиться на ; інакше ця остання конгруенція не має розв’язків, а значить система (2) несумісна. Нехай ділиться на . Розв’язуючи цю конгруенцію, дістанемо:

              Тоді сукупність усіх значень t1, що задовольняють другу конгруенцію, буде:

де  t2 пробігає всі цілі числа. Звідси дістаємо:

(5)

де задовольнятимуть перші дві конгруенції. Тепер з чисел (5), аналогічно, виберемо ті, які задовольнятимуть третю конгруенцію. Так знову або прийдемо до конгруенції відносно t2, яка не має розв’язків, а значить система (2) несумісна, або знайдемо, що значення

де t3 – ціле, або

задовольнятимуть перші три конгруенції і т.д. якщо дана система (3) сумісна, то кінець кінцем, за доведеним на початку, прийдемо до єдиного розв’язку цієї системи за модулем

Приклад. Розв’язати систему конгруенцій.

З першої конгруенції маємо , де - ціле число. Щоб визначити , підставимо значення у другу конгруенцію; тоді матимемо:

або, скорочуючи на 5 матимемо:

.

Звідси або , де - будь-яке ціле число.

Тепер

задовольнятиме дві перші конгруенції. З цих чисел виберемо такі , які б задовольняли й третю конгруенцію; для цього виберемо з умови:

звідки випливає:

або ,  де - будь-яке ціле число.

Отже, розв’язком даної системи буде або .

Зауважимо, що коли в системі (1) для деяких і ділиться на , тоді -та конгруенція системи (1) матиме розв’язків, і ми дістанемо кілька систем конгруенцій виду (2); тому, взагалі кажучи, система (1) матиме кілька розв’язків. Для складання систем виду (2) треба кожен розв’язок однієї конгруенції системи (1) скомбінувати з кожним розв’язком решти конгруенцій цієї системи.

3. Приклади розв’язання задач.              

Задача 10. Розв’язати такі системи конгруенцій:

              а)

Позначимо шукане число через x, тоді задача зведеться до розв’язання такої системи конгруенцій:

Маємо

,

Розв’язуючи допоміжні конгруенції

дістанемо:

Отже, за теоремою,

буде розв’язком заданої системи конгруенцій. Звідси випливає, що найменшим натуральним числом, яке  задовольняє умову задачі, буде x=58.

Відповідь:

б)

Позначимо шукане число через x, тоді задача зведеться до розв’язання такої системи конгруенцій:

Маємо

,

Розв’язуючи допоміжні конгруенції

дістанемо:

Отже, за теоремою,

буде розв’язком заданої системи конгруенцій. Звідси випливає, що найменшим натуральним числом, яке  задовольняє умову задачі, буде x=229.

Відповідь:

в)

Позначимо шукане число через x, тоді задача зведеться до розв’язання такої системи конгруенцій:

Маємо

,

Розв’язуючи допоміжні конгруенції

дістанемо:

Отже, за теоремою,

буде розв’язком заданої системи конгруенцій. Звідси випливає, що найменшим натуральним числом, яке  задовольняє умову задачі, буде x=2959.

Відповідь:

Завдання 11. Розв’язати такі системи конгруенцій.

Відповідь: система розв’язків не має, оскільки 2 конгруенція не має розв’язків, отже дана система несумісна.

Задача 12. Знайти числа, які:

              а) При діленні на 4, 5, 7 дають відповідно остачі 2, 3, 4.

Позначимо шукане число через x, тоді задача зведеться до розв’язання такої системи конгруенцій:

Маємо

,

Розв’язуючи допоміжні конгруенції

дістанемо:

Отже, за теоремою,

буде розв’язком заданої системи конгруенцій. Звідси випливає, що найменшим натуральним числом, яке  задовольняє умову задачі, буде x=18.

Відповідь:

              б) При діленні на 3, 7, 8 дають відповідно остачі 2, 4, 5.

Позначимо шукане число через x, тоді задача зведеться до розв’язання такої системи конгруенцій:

Маємо

,

Розв’язуючи допоміжні конгруенції

дістанемо:

Отже, за теоремою,

буде розв’язком заданої системи конгруенцій. Звідси випливає, що найменшим натуральним числом, яке  задовольняє умову задачі, буде x=53.

Відповідь:

Завдання 13. Знайти найменше натуральне число, яке кратне 7 і дає остачу 1 від ділення на 2, 3, 4, 5, 6.

1).  

2).

3).

4).

5).

Відповідь: найменше натуральне число 301.

Висновки

              Висновки

В роботі було вивчено поняття систем лінійних конгруенцій та її розв’язки. Досліджено умови існування розв’язків. Розглянуто способи розв’язанння систем лінійних конгруенцій. Розв’язано ряд відповідних задач.

Досліджено історію питання