Ознака подільності на 2, 3, 4,5,9.

На 2: для подільності числа на 2 необхідно і достатньо, щоб його остання цифра була парною; 3156:2.

На 3 і 9: необхідно і достатньо, щоб його сума цифр ділилась на 3(на 9);

8211:3=8+2+1+1=12:3.

На 4(на 25): необхідно і достатньо, щоб число, утворене двома його останніми цифрами ділилось на 4 (на 25); Напр.:(681732-на 4; 17675-на 25).

На 5: Необхідно і достатньо, щоб його остання цифра була 0 або 5. 1240:5.       

 

29. Прості і складені числа. Теорема про існування простого дільника у будь-якого натурального числа. Решето Ератосфена. Теорема про нескінченність множини простих чисел.
Число 1 має найменше дільників — лише один. Числа 2, З, 17 мають по два дільники: 1 і самого себе. Числа 4, 12, 21 і 30 мають більше, ніж два дільники. Натуральне число називають простим, якщо воно має тільки два різні дільники: одиницю і саме це число. Число, яке мас більше, ніж два дільники, називають складеним.. Якщо число має дільник, відмінний від 1 і самого себе, то це число має більше, ніж два дільники, і тому воно є складеним. Число 12 475 — складене, бо має дільником.
Теорема 20(Теорема про існування простого дільника у будь-якого натурального числа). Добуток кількох натуральних множників ділиться на просте число тоді і тільки тоді, коли хоч один із множників ділиться на просте число. Необхідність. Нехай p – довільне просте число і a1, a2,..., an – будь-які натуральні числа такі, що a1·a2·...·an M p. Достатність теореми випливає із теореми про подільність добутку.
Решето Ератосфена
Для знаходження простих чисел давньогрецький учений Ератосфен запропонував певний спосіб. Він виписував усі числа від 1 до якогось числа а. Викреслював число 1, яке не є простим. Підкреслював число 2 і викреслював усі числа, які діляться на 2, тобто числа 4, 6, 8,.... Наступне незакреслене число 3 є простим. Ератосфен підкреслював це число і викреслював усі числа, які діляться на 3. Підкреслював наступне невикреслене число 5, яке є простим, і т. д. У такий спосіб серед чисел, що не перевищують а, можна «висіяти» всі прості числа. Якщо «висіяти» всі прості числа, що не перевищують ЗО, то одержимо: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — перші 10 простих чисел.
Теорема (Евкліда): множина простих чисел нескінченна.
Доведення: проведемо методом від супротивного, припустивши, що множина простих чисел скінченна. Задамо цю множину переліком: А={p₁,p₂,p₃,…p_k}, де вони записані у порядку зростання. Утворимо нове число b=p₁·p₂·p₃·…·p_k+1. Легко бачити, що b>1, а тому, згідно з теоремою про існування простих чисел, число b буде мати відмінний від 1 простий
дільник. Нехай це буде число p. Оскільки, p – дільник числа b, то . Оскільки p – просте число, то pєА. Тоді за теоремою про подільність добутку цей добуток буде ділитись націло на p. Це означає, що число p дорівнює якомусь елементу з множини А.
Тоді справедливим буде твердження: (p₁·p₂·p₃·…·p_k) р, бо там записані всі прості числа. Нехай для визначеності р=р₂, тоді . Оскільки і , то за теоремою про подільність різниці, різниця (в-p₁·p₂·p₃·…·p_k) p₂, тобто 1 p₂. Це суперечить тому, що р₂>1. Ця суперечність і говорить, що наше припущення про скінченність множини простих чисел було хибним. Теорема доведена.

30. Спільне кратне, найменше спільне кратне. Спільний дільник, найбільший спільний дільник. Взаємно прості числа. Властивості найменшого спільного кратного і найбільшого спільного дільника.
Будь-яке натуральне число, яке ділиться на дане натуральне число, називають кратним даному числу.
Найменшим спільним кратним двох натуральних чисел називають найменше натуральне число, яке ділиться на кожне з даних чисел .(НСК)
Щоб знайти найменше спільне кратне чисел а і b, потрібно виписати всі прості множники, які входять принаймі в один розклад, причому кожний з них треба взяти з найбільшим показником, з яким він входить у канонічні розклади даних чисел(НСК(900,990)2²*3²*5²*11=9900)
Натуральне число, на яке ділиться кожне з даних натуральних чисел називається спільним дільником цих чисел. Найбільше натуральне число, на яке ділиться число а і Ь, називається найбільшим спільним дільником (НСД) цих чисел. Щоб знайти НСД двох (або більшої кількості) чисел, треба розкласти ці числа на прості множники і знайти добуток спільних простих множників(НСД (180; 450) = 2 ∙ З ∙ 3 Числа a і b називаються взаємно простими, якщо НСД (a; b) = 1.
Наприклад: числа 3 і 5 взаємно прості, бо НСД (3; 5) = 1
Властивості НСД(a;b) і НСК(a;b):
1) (a;b)⟹НСД(a;b)=b, НСК(a;b)=а;
2) кожне спільне кратне даних чисел ділиться на їхнє найменше спільне кратне;
3) найбільший спільний дільник кількох чисел ділиться на будь-який їхній спільний дільник;
4)НСД(a;b)*НСК(a;b)=a*b, звідки НСК(a;b)= a*b/НСД(a;b)
5)НСД(a;b)=1⟹НСК(a;b)= а*b

31. Ознака подільності на складені числа.
Ознака подільності на 6: Для того, щоб число ділилося на 6, необхідно і достатньо, щоб воно ділилося на 2 і 3.
Ознака подільності на 12: Для того, щоб число ділилося на 12, необхідно і достатньо, щоб воно ділилося на 3 і 4.
Ознака подільності на 15: Для того, щоб число ділилося на 15, необхідно і достатньо, щоб воно ділилося на 3 і 5.
Теорема про подільність на складені числа: Для того, щоб натуральне число ділилось на складене число n = bc, де НСД (b,c) = 1, необхідно і достатньо, щоб воно ділилося на b і с.
Доведення цієї теореми аналогічне доведенню ознаки подільності на 6.(Для того, щоб число а ділилося на 6, необхідно й достатньо, щоб воно ділилося на 2 і на 3)
Зауважимо, що дану теорему можна застосовувати багаторазово.
Так, щоб число ділилося на 60, необхідно і достатньо, щоб воно ділилося на 4 і на 15. У свою чергу, щоб число ділилися на 15, необхідно і достатньо, щоб воно ділилося на 3 і на 5. Отже, для того, щоб число ділилося на 60, необхідно і достатньо, щоб воно ділилося на 4, на 3 і на 5

 

32. Основна теорема арифметики. Знаходження НСД і НСК чисел, які задані у канонічному виді.
В теорії чисел основна теорема арифметики стверджує, що будь-яке натуральне число більше одиниці може бути представлене у вигляді добутку простих чисел і таке представлення є єдиним з точністю до порядку множників. Для знаходження розкладу натурального числа на прості множники послідовно застосовується операція ділення числа на прості числа починаючи з найменшого. Причому, перехід до наступного більшого простого числа виконується тільки при неможливості цілого ділення на менше. Так, наприклад, можна отримати наступні розклади чисел 420 та 1200: Згідно з основною теоремою арифметики стверджується, що ці представлення є унікальними для кожного числа, тобто не існує розкладів з іншим набором чисел або іншою кількістю однакових множників.
Відрізнятися може лише порядок множників, але, внаслідок комутативності та асоціативності множення, всі такі розклади є еквівалентними. Таким чином, теоремою стверджується, що не існує таких чисел, які можна було б розкласти на прості множники різними способами.
Знайдемо НСК і НСД чисел 360 і 525. Ці числа можна подати у канонічному вигляді: 360 = 2³ ∙ 3² ∙ 5; 525 = 3 ∙ 5² ∙ 7. У розклад на прості множники НСД цих чисел повинні ввійти всі спільні прості множники, причому кожний з них треба взяти з найменшим показником, з яким він входить в канонічні розклади даних чисел. Отже НСД(360, 525) = 3 ∙ 5 = 15.
У розлад на прості множники НСК (360, 525) повинні ввійти всі прості множники, які входять принаймні в один розклад, причому кожний з них треба взяти з найбільшим показником. НСК(360, 525) = 2³ ∙ 3² ∙ 5² ∙ 7 = 12 600.
Теорема: НСК (а, b) ∙ НСД (а, b) = а ∙ b.
Наслідок: Якщо НСК (а, b) = 1, то НСК (а, b) = а ∙ b.

 

33. Поняття про алгоритм. Алгоритм Евкліда.
Алгоритмом називається точна послідовність дій, які забезпечують одержання потрібного результату з вихідних даних. Алгоритми призначені для виконання його або ж людиною або ж автоматичним пристроєм.
Алгоритми записуються у вигляді форм представлення:
словесна (запис природньою мовою)
графічна (графічні символи)
псевдокоди (містять у собі і елементи мови програмування, і фрази природної мови, і загальноприйняті математичні позначення)
програмна (тексти на мовах програмування)
Теорема 10 (алгоритм Евкліда) Якщо a=b*q+r, 0≤r<b, де a,b,q,r∈ N_0, то НСД(a;b)=НСД(a;b)
На основі цієї теореми будується спадна послідовність чисел. У якій першим елементом є більше з двох даних чисел, другим - менше, третім-остача від ділення першого числа на друге, четвертим – остача від ділення другого числа на третє і т.д., поки не дістанемо ділення без остачі. Дільник при останньому діленні є найбільшим спільним дільником даних чисел.