Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Теорія подільності на множині цілих чисел.doc
Скачиваний:
35
Добавлен:
14.02.2016
Размер:
591.36 Кб
Скачать

Посібник укладено у відповідності з діючою програмою курсу "Алгебра і теорія чисел" для фізико-математичних факультетів вищих педагогічних навчальних закладів і рекомендовано для студентів II курсу спеціальності "Математика та інформатика". Він охоплює основні питання розділу "Теорія подільності" курсу теорії чисел, містить приклади розв'язування основних типів задач, завдання для самостійної роботи студентів та варіанти контрольних робіт.

Посібник підготувала Русіна Л. В.

ЗМІСТ

1.Ділення на множині цілих чисел.......................................2

2.Найбільший спільний дільник. Алгоритм Евкліда. .......4

3.   Найменше спільне кратне................................................8

4.   Прості і складені числа...................................................10

5.   Варіанти контрольних робіт..........................................16

РЕКОМЕНДОВАНА ЛІТЕРАТУРА

1. Алгебра і теорія чисел. Практикум, ч. 2. — К. 1986

2. Бородін О. І. Теорія чисел. — К. 1970.

3. Бухштаб А. А. Теория чисел. — М. 1966.

4. Завало С. Т. та ін. Алгебра і теорія чисел, ч. 2. — К. 1980.

5. Михелович Ш. X. Теория чисел. — М. 1967.

1. Ділення на множині цілих чисел.

1. Відношення подільності та його властивості.

Означення: Ціле число а ділиться на ціле число b 0. якщо існує таке ціле число с, що а = b∙с.

Число а називається діленим, b дільником, с часткою. Якщо а ділиться на b, це позначають і кажуть, що а кратнедо b.Відношення подільності є бінарним відношенням на множині цілих чисел Z і має такі властивості:

1)Відношення подільності рефлексивне: .

2)  Відношення подільності транзитивне: з іслідує.

3)  Якщо , тоі, тобто відношення подільності зберігається при заміні знаків діленого і дільника.

4)  Якщо і, тоі.

5)  Якщоі , то

6)  Нуль ділиться на будь-яке b≠0.

7)  Будь-яке а ділиться на 1.

8)  Якщо а≠0, то не існує такогоq, що0∙q =а, тобто ділення на 0 неможливе.Всі ці властивості легко доводяться на основі означення.

2. Ділення з остачею.

Означення: Число а ділиться на b≠0 з остачею, якщо існують такі числа q та r, такі, що а = bq + r, де 0 ≤ r <|b|.

Число q називається неповною часткою, r остачею.

Теорема: Які б не були цілі числаа іb ≠ 0, завжди можливо і при тому єдиним способом поділитиа наb з остачею.

Доведення: І. Покажемо, що завжди існують такі q та r , що а=bq + r для двох різних випадків.

1) Нехай а — довільне ціле число, а b > 0. Запишемо множину всіх чисел, кратних b:

...,b(-2), b(-1), b0, b∙1, b∙2....

Серед цих чисел є число bq — найбільше кратне b, яке не перевищує а, тоді а ≥ bq і а<b∙(q+1), тобто bq < а < bq + b. Віднімемо від усіх частин нерівності bq, отримаємо 0 ≤ а - bq <b. Позначимо число а - bq = r, звідки а = bq + r, 0 ≤ r < b.

2)  Нехай а — довільне ціле число, b < 0. Оскільки b < 0, то (-b) > 0 і згідно з випадком 1) ділення а на -b можливе, тобто існують q та r такі, що а = (-b)∙q + r, де 0 ≤ r < (-b) або 0 ≤ r < |b| .

II. Доведемо тепер єдиність ділення з остачею методом від супротивного. Нехай існують дві частки і дві остачі і такі, що

а = b+, 0≤<b;

а = b+, 0≤<b.

(Для простоти вважаємо, що b > 0). Тоді

b+= b+ або b∙(-)=- (*).

Оскільки 0≤<b і 0≤<b, то -b, але в цьому випадку рівність (*) можлива лише тоді, коли - = 0, тобто =. Отримуємо рівність b∙(-) = 0 і оскільки b ≠ 0, то -= 0, тобто =.

Отже, теорему доведено.

3. Задачі:

1.  Довести властивості відношення подільності 1) — 8).

2.  Доведіть, що

1)   з трьох послідовних натуральних чисел одне ділиться на 3;

2)   з двох послідовних парних чисел одне ділиться на 4;

3)   з п'яти послідовних натуральних чисел одне ділиться на 5;

4)   добуток трьох послідовних чисел ділиться на 6;

5)   добуток п'яти послідовних чисел ділиться на 120.

3.  Нехай а = -1284, b = 148. Вкажіть таке q, що bqа < b∙(q+1).

4.  Нехай а = - 135, Ь = 14. Вкажіть таке г, що 0 < г < \ Ь \(а- г)\Ь.

5.  Вкажіть частку і остачу від ділення:

1) 5 на 7; 2) 120 на 13; 3) -529 на -23; 4) -410 на 47; 5) 256 на -15.

6.   Відомо ділене а і остача r, знайти дільник b і частку д, якщо:

1) а = 100, r = 6; 2) а = 148, r = 37; 3) а = 497, r = 16.

7.   Відомо а та q , знайти b і r, якщо:

1) а = 371, q =14; 2) а = 3129, q = 83; 3) а = 13127, q = 121; 4) а = 42157, q = 231.