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

     ♦ ділимо 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; і т. д,, до тих пір поки не зустрінеться найбільше просте число .