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

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

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

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

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

Виконав

студент групи І-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₁, якщо , то маємо остачу ;

     ♦ ділимо r₁ на r₂ І знову можливі два випадки: якщо , то (r₁,r₂)=(b,r₁)=(a,b), або r₁ ділиться на r₂ з остачею r₃ і т.д.

     Оскільки  остачі, які отримуються в процесі ділення, то вони є спадними натуральними числами, і на якомусь кроці ми отримаємо остачу, рівну 0, а остання, не рівна 0 остача, і буде найбільшим спільним дільником чисел а і b. Це твердження може бути сформульовано у вигляді теореми.

     Теорема: Якщо

     ….

     то  (а; b) = r_n

     Доведення: На основі леми 2 отримуємо з першого рядка (а, b)=(b, r1), з другого: (b, r₁) = (r1, r2) і т.д. Отже, (а, b) = (r_n-1,r_n). Але і на основі леми 1 = r_n а тому (а, b) =r_n. 

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

     Означення: Нехай а і b цілі числа, відмінні від 0. Ціле число k називається спільним кратним цих чисел, якщо воно ділиться на а і на b.

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

     1) К – спільне кратне а і b;

     2) будь-яке спільне кратне цих  чисел ділиться на К.

     Найменше  спільне кратне позначається К = [а, b] або НСК (а, b).

     Теорема: Число , де (а,b) – найбільший спільний дільник двох натуральних чисел а і b, є найменшим спільним кратним цих чисел.

     Доведення: Нехай (a, b)=d, тоді а=n∙d, b=l∙d, де (n;l)=1. Отже

     Ця  рівність показує, що ділиться на b і на а, тобто є спільним кратним a і b. Покажемо тепер, що будь-яке кратне К>0 чисел а і b ділиться на . Оскільки , то K=а∙s = n∙d∙s. Крім того і b=l∙d тому , а отже . Оскільки (n,l)= 1, то ; отже існує таке число k, що .

     Тоді  К = nds = ndlk і оскільки , то K ділиться на . Отже, К = – найменше спільне кратне чисел а і b.

     Для спрощення знаходження НСК варто  знати такі його властивості:

     Якщо  кожне з чисел а і b помножити або поділити на одне й те ж число , то їх НСК також помножиться або поділиться на це число m:

     Завдання.

     1) Знайти НСД чисел за допомогою  алгоритма Евкліда

     а) 2585,   7975

     б) 42628,   33124

     в) 71004,   154452

     г) 179370199,   4345121

      Приклад.

     а)  
 
 
 
 
 
 
 

     Остання відмінна від нуля остача – 55 є НСД. Для перевірки отриманих результатів можна скористатись програмою, запропонованою в Додатку А.

     2) Знайти НСК чисел

     а) 364, 143

     б) 120, 96

     в) 71004, 154452

     г) 67283, 122433, 221703

     Для перевірки отриманих результатів  можна скористатись програмою, запропонованою в Додатку А.

     3) [x,y] = 336, (x,y)=12. Знайти все можливі пари x, y, для яких виконується дана умова.

     Розкладемо  НСД та СНК на множники. НСК: 2∙2∙2∙2∙3∙7 НСД: 2∙2∙3. З утворених множників  вибираємо комбінації, які влаштовують  умови НСД і НСК: 336 = 2∙2∙2∙2∙3∙7, 12= 2∙2∙3;  48 = 2∙2∙2∙2∙3, 84 = 2∙2∙3∙7.

     4) [x,y] = 168, (x,y) = 24. x,y =?

     5) [x,y] = 210, (x,y) = 15. x,y =? 
 
 

     2. ПРОСТІ І СКЛАДЕНІ ЧИСЛА

     2.1. Прості числа і їх властивості.

     Означення: Натуральне число p називається простим, якщо воно більше за 1 і не має інших дільників, крім 1 і р.

     Означення. Натуральне число називається складеним, якщо воно більше за 1 і має. принаймні, один дільник, відмінний від 1 та р.

     Число 1 не належить ні до простих, ні до складених  чисел. Першими простими числами в натуральному ряді є 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,37,41.

     Таким чином, множина всіх натуральних  чисел розбивається на три підмножини:

     1) прості числа

     2) складені числа

     3) число 1.

     Основним  фактом теорії простих чисел є  твердження про те, що будь-яке складене число розкладається і при тому єдиним способом (з точністю до порядку запису) в добуток простих чисел. Розглянемо деякі властивості простих чисел.

     1. Якщо просте число ділиться  на деяке натуральне  , то p=n.

     Доведення. Припустимо, що , але оскільки просте число ділиться тільки на 1 та самого себе, то дане припущення не вірне, тому p=n.

     2. Якщо p₁ і p₂ – різні прості числа, то р₂ не ділиться на р₂.

     Доведення. Припустимо, що p₁ ділиться на p_2, але за означенням просте число ділиться тільки на 1 та самого себе, тому дане припущення не вірне, і р₂ не ділиться на р_2.

     З. Будь-яке натуральне число n>1 ділиться хоча б на одне просте число.

     Доведення. Будь-яке натуральне число > 1 є або простим або складеним числом. Якщо воно є простим числом, то ділиться на себе, а отже на просте число. Якщо воно складене, то ділиться хоча б на одне менше за p. Дане число в свою чергу або є простим або маю ще один дільник. Оскільки кожний наступний дільник є меншим за попередній, то настане момент, коли дільником буде  тільки 1. Останнє число, яке отримується перед одиницею буде, простим, оскільки крім одиниці ділиться тільки на себе.

     4. Якщо n – натуральне число, а р – просте, то або n ділиться на p, або n i p — взаємнопрості.

     Доведення. Розглянемо (p,n). Якщо (p,n) = 1, то дані числа взаємно прості. Якщо , то оскільки в p немає інших дільників крім 1 та його самого, то .

     5. Якщо добуток двох або більше  натуральних чисел ділиться на  просте число р. то хоча б один з множників ділиться на р.

     6. Якщо натуральне число n складене, а р його найменший простий дільник, то .

     Доведення: Оскільки n — складене число, а р — його найменший простий дільник, то n=pn₁, причому . Помножимо обидві частини нерівності на рівні числа pn₁ і n. Отримаємо , звідки , або .

     Наслідок: Якщо число n не ділиться на жодне просте число, яке не перевищує , то n – просте, в протилежному випадку – воно складене. 

     2.2. Розклад складених чисел на прості множники.

     Теорема (основна теорема арифметики).

     Будь-яке  натуральне число > 1 або є простим, або може бути представлене, і, притому єдиним способом у вигляді добутку простих чисел.

     (Два  представлення, які відрізняються  лише порядком розміщення множників,  вважаються однаковими).

     Доведення:

     I. Існування розкладу.

     Нехай n = 2. Оскільки 2 — просте число, то для n = 2 твердження теореми є справедливим.

     Припустимо, що твердження справедливе для всіх натуральних чисел, які більші, або  рівні 2, але менші деякого n, і доведемо справедливість твердження для цього n.

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

     де і

     Для чисел n₁ і n₂ згідно з індуктивним припущенням буде справедливим

     Тоді , тобто існування розкладу для довільного n доведено.

     II. Єдиність розкладу.

     Нехай n = 2, це просте число, отже його розклад єдиний.

     Припустимо, що розклад на прості множники єдиний для всіх натуральних чисел, більших 2, але менших n, і доведемо єдиність розкладу для n.

     Якщо  n – просте число, то очевидно, що його розклад також є єдино можливим. Нехай n – складене. Припустимо, що його можна розкласти на прості множники двома різними способами:

     Тоді

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

     Оскільки  q₁ – просте число і р₁ > 1, то q₁ = p₁.

     Поділимо  обидві частини рівності на q₁ = p₁, і отримаємо

     Оскільки і – числа, менші за n, то згідно індуктивного припущення з останньої рівності випливає, що

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

     Згідно  з основною теоремою арифметики будь-яке  складене число n > 1 можна представити у вигляді добутку простих чисел. Серед цих простих множників можуть зустрічатись однакові. Нехай, наприклад, р₁ зустрічається a₁ раз, р₂ — a₂ раз, ... , р_k — a_k раз, тоді розклад числа n на прості множники можна записати таким чином

                                          (*)

     Множники  р_1, р_{2, …} р_k переважно розміщуються в порядку зростання. Перетворення натурального числа n до виду (*) називається факторизацією числа, а сама форма (*) — канонічною. 

     2.3.Нескінченість множини простих чисел. Решето Ератосфена.

     Теорема Евкліда. Множина простих чисел нескінчена.

     Доведення (від супротивного). Припустимо, що множина простих чисел скінченна; нехай це будуть числа р₁, р₂, ... , р_k, де p_k — найбільше просте число. Утворимо добуток чисел р₁р₂...р_k і розглянемо натуральне число n=р₁р₂...р_k+1. Оскільки n > p_k то n повинно бути складеним, отже воно повинно ділитись на одне з чисел р₁р₂...р_k, нехай на р₁. Оскільки добуток р₁р₂...р_k ділиться на р₁ також, то й другий доданок, тобто 1, також повинен ділитись на p₁, але це неможливо.

     Отже  наше припущення невірне, а тому множина  простих чисел нескінчена.

     Решето  Ератосфена. В III ст. до н. є. грецький математик Ератосфен знайшов спосіб виділення простих чисел з будь-якої скінченної послідовності натуральних чисел 1, 2, З, ..., n за допомогою послідовного викреслювання числа 1; всіх чисел кратних 2; всіх чисел кратних 3; і т. д,, до тих пір поки не зустрінеться найбільше просте число .