Теорія подільності на множині цілих чисел

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

імені В.Гнатюка 
 
 
 
 
 
 
 

Курсова робота

“Теорія подільності на множині цілих чисел” 
 
 
 
 
 

Виконав

студент групи І-34

Романишин Сергій 
 
 
 
 
 
 
 

Тернопіль, 2007

Вступ

     Дана  курсова робота присвячена вивченню теорії подільності на множині цілих чисел. Дана тема є актуальною і маю навчально-пізнавальний характер.

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

     Об’єм і структура. Курсова має об’єм 24 друкованих аркуші, містить вступ, два основні розділи та два додатки.

 

Зміст 

 

 

      1.ДІЛЕННЯ НА МНОЖИНІ ЦІЛИХ ЧИСЕЛ.

     1.1. Відношення подільності та його властивості. Ділення з остачею.

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

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

     Відношення  подільності  є бінарним відношенням на множині цілих чисел Z і має такі властивості:

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

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

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

     4) Якщо  і , то і

     5) Якщо  і bєZ, то .

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

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

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

     Число а ділиться на з остачею, якщо існують числа q та r, такі, що , де .

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

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

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

     1) Якщо а – довільне ціле число, a b > 0, то множина всіх чисел, кратних b:

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

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

     а = b∙q + r, де

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

      ,  

      ,  

Нехай b > 0, тоді

     

     Оскільки , то , але тоді рівність можлива тільки коли r₁ = r₂.

     Отримуємо рівність і оскільки , то = 0,

     тобто q₁ = q₂.

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

     Завдання.

1. Вказати частку і остачу від ділення

     а) 5 на 7

     б) 120 на 13

     в) -529 на -232

2. Відомо ділене a і остача r, знайти дільник b і частку q

     а) a =100, r=6

     б) a = 148, r = 37

     в) a=497, r =16

     Приклад. а) a = bq +r; =>  bq=100-6=94, b > 6

     b = 47, q = 2;

3. Використовуючи властивості відношення подільності записати кілька чотирицифрових чисел, що діляться одночасно на 4,5,9.

     Приклад. 1080 – ділиться на 5 оскільки цифра наймолодшого розряду 0, на 9, оскільки сума цифр всіх розрядів кратна 9.

4. а) Перша зліва цифра чотирицифрового числа 7. Якщо її переставити на останнє місце, то буде число, яке на 864 менше за початкове. Знайти початкове число.

     Приклад. 7000 + 100а + 10b + c – 1000a + 100b + 10c + 7 = 864

     c – 7 = 4; c=1

     b -1 – c = 6; b=8

     a-b = 8  a=6

     б) Перша зліва цифра чотирицифрового числа 6. Якщо її переставити на останнє місце, то буде число, яке на 855 менше за початкове. Знайти початкове число.

     в) Перша зліва цифра шестицифрового числа 1. Якщо її переставити на останнє місце, то буде число, яке втричі більше за початкове. Знайти початкове число.

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

           5) Чи може різниця двох трицифрових чисел, з яких друге записане тими самими цифрами, що й перше, але у зворотному порядку, бути квадратом якого-небудь натурального числа?

     Розпишемо дані числа порозрядно. Отримаєм 100a+10b+c і 100c+10b+a. Їх різниця рівна  99(a-c) = 3²∙11(a-c). Отже, (a-c) повинно бути рівним 11, проте, це не можливо, оскільки a та c – одноцифрові числа.

     6) Знайти найменше натуральне число, яке при множенні на 2 стає, квадратом, а при множенні на 3 — кубом натурального числа.

     Таке  число повинно розкладатися на множники 2³ і 3². Отже це число 72: 72∙2 = 12²  72∙3=6³.

     7) Знайти остачу при діленні 21¹⁸ + 24¹⁹ + 45⁷ на 15.

     Щоб число ділилось на 15 потрібно, щоб  воно ділилось на 3 і на 5 одночасно. Кожен з доданків ділиться на 3, оскільки сума цифр кожного з них ділиться на 3. Число ділиться на 5, якщо цифра його молодшого розряду 0 або 5. Наймолодший розряд в 21¹⁸ = 1, оскільки він не змінюється при піднесенні до степеня, молодший розряд в 45⁷ = 5, оскільки він також не змінюється, в 24ⁿ наймолодший розряд чергується відповідно до степеня: при непарних степенях – 4, при парних – 6. Отже, наймолодший розряд 24¹⁹ = 4. 4 + 5 + 1 = 10, отже, наймолодший розряд суми дорівнює 0, тому дане число ділиться на 5, а отже і на 15.

     8) Знайти остачу при діленні:

     а) 21²⁰ + 24¹⁸ на 5; на 10;

     б) 21²⁰ + 9∙24¹⁸ на 5; на 10.  

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

     Означення: Ціле число називається спільним дільником цілих чисел a і b, якщо кожне з цих чисел ділиться на d.

     Ціле  число D називається найбільшим спільним дільником чисел а і b, якщо:

     1) D – спільний дільник а і b;

     2) D – ділиться на будь-який спільний дільник а і b. Позначається D=(a,b) або НСД(a,b).

     Два числа а і b називаються взаємнопростими. якщо (а, b)=1.

     Теорема: Найбільший спільний дільник чисел а і b визначається однозначно точністю до знаку.

     Доведення: Нехай d₁ i d₂ – найбільші спільні дільники чисел а і b. Оскільки d₁=(a, b), то він ділиться на будь-який інший дільник, тобто . Аналогічно . Згідно означення , тобто і навпаки, , тобто .

     З цих двох нерівностей випливає, що , тобто d₁=d₂ або d₁=–d₂.

     Приклад: Знайдемо НСД чисел а=135 і b=–180. Множина всіх додатних дільників 135 має вигляд:

     А = {1,3, 5, 9, 15,27,45,135},

     а для числа 180:

     В = {1,2,3,4,5,6, 9, 10, 12, 15, 18,20,30,36,45.60,90, 180}.

     Спільними дільниками є

     А ПВ = {1,3, 5,9, 15,45}.

     Отже  число 45 є найбільшим спільним дільником  цих чисел.

     З цього прикладу видно, що шукати таким  методом НСД незручно, особливо для  великих чисел, найчастіше застосовують для цього спосіб, запропонований видатним давньогрецьким математиком  — Евклідом.

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

     Для обґрунтування алгоритму Евкліда доведемо дві леми:

     Лема 1. Якщо , то (а, b)= b.

     Доведення. Якщо і , то b — спільний дільник а і b. Візьмемо довільний спільний дільник а і b – с, очевидно, що , тому за означенням b є НСД а і b.

     Лема 2. Якщо a = bq + r, де a, b і r відмінні від 0, то (a,b)=(b,r).

     Доведення. Нехай d — спільний дільник а і b, тоді і . За умовою а = bq + r, звідки r = a – bq. Якщо зменшуване і від'ємник ділиться на d, то і різниця буде ділитися на d, тобто . Тому будь-який спільний дільник а і b буде також дільником r. Аналогічно доводиться, що будь-який спільний дільник b і r буде також дільником а і b. Це означає, що множина всіх дільників а і b співпадає з множиною всіх дільників b і r, а отже будуть співпадати і їх найбільші дільники.

     Алгоритм  Евкліда для знаходження НСД чисел а і b полягає у виконанні наступних дій:

     ♦ ділимо число а на b, якщо , то за лемою 1 (а, b) = b. якщо

      , то отримуємо остачу ;

     ♦ ділимо b на r₁, якщо , то (b,r₁)= r₁, і згідно з лемою 2 (а,b)=(b,r₁)=r₁, якщо , то маємо остачу ;