Якщо a:b=c(ост.r), то a=bc+r
Подільність натуральних чисел
Натуральне число є дільником натурального числа , якщо
де — натуральне число. У цьому разі кажуть, що число ділиться без остачі на число Зазначимо, що з рівності випливає, що число також ділиться без остачі і на число тобто — дільник числа . Наприклад, 5 і 3 — дільники числа 15.
Нагадаємо, що натуральні числа, які діляться на 2, а також число 0, називаються парними, а натуральні числа, що не діляться на 2, — непарними.Кратним числа називають число яке ділиться без остачі на Множина чисел, кратних даному число нескінченна.
Теорема. Якщо кожний доданок ділиться на певне число, то їхня сума також ділиться на це число.
Наслідок. Якщо сума двох доданків і одне з них діляться на деяке число, то й інший доданок ділиться на це число.
Зауваження. Не слід думати, що коли кожний доданок суми не ділиться на деяке число, то й сума не ділиться на це число. Наприклад, сума 23 + 13 ділиться на 6, хоча жодний із доданків не ділиться на це число.
Теорема.Якщо зменшуване і від'ємник діляться на деяке число, то і різниця поділиться на це число.
Теорема.Якщо кожний доданок, крім одного, ділиться на деяке число, а той один на нього не ділиться, то й сума не поділиться на це число.
Теорема. Якщо хоча б один із множників ділиться на дане число, то їхній добуток також ділиться на це число.
Зауваження. Умова теореми є достатньою, але не необхідною для подільності добутку на число. Наприклад, добуток 1427 ділиться на 21, хоча ні 14, ні 27 на 21 не ділиться.
Теорема. Якщонатуральне число а ділиться на добуток двох натуральних чисел, то воно поділиться на кожне з цих чисел окремо.
Теорема. Якщо натуральне число а ділиться окремо на два натуральних числа b і с, причому b і с не мають спільних дільників, крім одиниці, то а ділиться на добуток bс.
Взаємно-прості та прості числа. НСК ТА НСД.Ознаки подільності натуральних чисел
Взаємно прості та прості числа
Означення. Натуральне число називається простим, якщо воно має рівно два натуральні дільники.
Якщо прості числа виписувати в ланцюжок за зростанням, то його початок буде такий: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... .
Взаємно простими числами називаються числа і , у яких найбільший спільний дільник дорівнює 1.
Критерії взаємної простоти двох цілих чисел: числа та взаємно прості тоді й тільки тоді, коли існують такі цілі числа і , що .
Властивості:
- Якщо кожне з чисел і взаємно просте з числом , то добуток також взаємно простий з .
- Якщо добуток ділиться на і при цьому взаємно просте з , то тоді на обов'язково ділиться число
Теорема. Існує безліч простих чисел.
Лема. Якщо і — різні прості числа, то вони взаємно прості.
Теорема. (Основна теорема арифметики). Будь-яке натуральне число, крім одиниці, може бути єдиним способом подане у вигляді добутку простих чисел (якщо не враховувати порядок розміщення множників).
Нехай складене число а розкладено в добуток простих чисел, серед яких можуть бути й рівні між собою. Записуючи добуток однакових множників у вигляді степеня, дістаємо
де — різні прості дільники числа а; — деякі цілі додатні числа, що дорівнюють кількості повторів простих дільників у розкладі числа а. Наведену рівність називають канонічним розкладом натурального числа а на прості множники.
Задача 1.
Довести, що коли a i b є Z, то ab(a2-b2) ділиться на 3.
Доведення. ab(a2-b2)=ab(a-b)(a+b). Якщо a i b діляться на 3, то ab(a2-b2) ділиться на 3; Якщо a i b мають однакові остачі, то (a-b) ділиться на 3; Якщо a i b мають різні остачі, то r1=1, r2=2діляться на 3, то ab(a2-b2) ділиться на 3;
Задача 2.
Довести, що 106 і 104 дають однакову остачу при діленні на 11.
Доведення. 106 - 104=104 (100 - 1)=99*104 діляться на 11, тому різниця цих чисел закінчується 0, а самі числа мають однакові остачі.
Задача 3.
Із семи аркушів паперу деякі розрізали на 7 частин, потім знову ще кілька аркушів розрізали на 7 частин і т.д. Чи можна у такий спосіб отримати 1984 аркуш.
Доведення. За кожним разом кількість аркушів збільшується на 6. Якщо всього розрізали k аркушів, то кількість аркушів стане 7+6k. Розглянемо рівність 6k+7=1984. Число 1984 при діленні на 6 має остачу 4, а не 7. Тому рівність неможлива.
Задача 4.
Довести, що якщо а - непарне число, то а2 - 1 ділиться на 8.
Доведення. a2-1=(а-1)(а+1). За умовою а - непарне, тому а-1 і а+1 - парні, тому
(а-1)(а+1) ділиться на 4. Нехай а=2k+1. Тоді (2k+1)2-1=4k2+4k+1-1=4(k2+k). Числа k2 і k мають однакову парність. Якщо k- парне, то k2+k - парне.
Якщо k- непарне, то k2+k - парне. Тому, a2-1 ділиться на 8. Доведено.
Теореми про остачі при діленні степенів на натуральні числа.
Теореми про остачі при діленні степенів на натуральні числа.
Варто мати на увазі, що квадрати цілих чисел при діленні на 2, 3 або 4 можуть давати остачі лише 0 та 1, куби при діленні на 9 - лише 0, 1 та 8. (Перевірте це самостійно). Подібні факти в поєднанні з вдалим вибором числа, остачі при діленні на яке ми розглядаємо, часто допомагають розв'язуванню. З допомогою такого вдалого вибору можна доводити, що число не є простим, можна розв'язувати рівняння в цілих числах.
Квадратні лишки
Остачі при діленні квадратів на натуральні числа.
Якщо квадрат натурального числа, тобто, m2 = m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1
4, то отримаємо остачі 0, 1;
5, то отримаємо остачі 0, 1, 4;
6, то отримаємо остачі 0, 1, 3, 4;
7, то отримаємо остачі 0, 1, 2, 4;
8, то отримаємо остачі 0, 1, 4;
9, то отримаємо остачі 0, 1, 4, 7;
10, то отримаємо остачі 0, 1, 4, 5, 6, 9;
11, то отримаємо остачі 0, 1, 3, 4, 5, 9;
12, то отримаємо остачі 0, 1, 4, 9;
13, то отримаємо остачі 0, 1, 3, 4, 9, 10, 12;
14, то отримаємо остачі 0, 1, 2, 4, 8, 9;
15, то отримаємо остачі 0, 1,4, 6, 9, 10;
16, то отримаємо остачі 0, 1, 4, 9;
17, то отримаємо остачі 0, 1, 4, 8, 9,15.
Кубічні лишки
Остачі при діленні кубів на натуральні числа.
Якщо куб натурального числа, тобто, m3 = m∙m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1, 2;
4, то отримаємо остачі 0, 1, 3;
5, то отримаємо остачі 0, 1, 2, 3, 4;
6, то отримаємо остачі 0, 1, 2, 3, 4, 5;
7, то отримаємо остачі 0, 1, 6;
8, то отримаємо остачі 0, 1, 3, 5, 7;
9, то отримаємо остачі 0, 1, 8;
10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9
Четвіркові лишки
Остачі при діленні четвертих степенів на натуральні числа.
Якщо четверту степінь натурального числа, тобто, m4 = m∙m∙m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1
4, то отримаємо остачі 0, 1;
5, то отримаємо остачі 0, 1;
6, то отримаємо остачі 0, 1, 3, 4;
7, то отримаємо остачі 0, 1, 2, 4;
8, то отримаємо остачі 0, 1;
9, то отримаємо остачі 0, 1, 4, 7;
10, то отримаємо остачі 0, 1, 5, 6;
П’ятіркові лишки
Остачі при діленні п’ятих степенів на натуральні числа.
Якщо п’яту степінь натурального числа, тобто, m5 = m∙m∙m∙m∙m, поділити на:
2, то отримаємо остачі 0, 1;
3, то отримаємо остачі 0, 1, 2;
4, то отримаємо остачі 0, 1, 3;
5, то отримаємо остачі 0, 1, 2, 3, 4;
6, то отримаємо остачі 0, 1, 2, 3, 4, 5;
7, то отримаємо остачі 0, 1, 2, 3, 4, 5, 6;
8, то отримаємо остачі 0, 1, 3, 5, 7;
9, то отримаємо остачі 0, 1, 2, 4, 5, 7, 8;
10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.
Розв’язування числових задач
n
|
n2
|
n3
|
n4
|
n4k
|
nk
|
...1
|
1
|
1
|
1
|
1
|
1
|
2
|
4
|
8
|
6
|
6
|
2,4,8,6
|
3
|
9
|
7
|
1
|
1
|
3,9,7,1
|
4
|
6
|
4
|
6
|
6
|
4,6
|
5
|
5
|
5
|
5
|
5
|
5
|
6
|
6
|
6
|
6
|
6
|
6
|
7
|
9
|
3
|
1
|
1
|
7,9,3,1
|
8
|
4
|
2
|
6
|
6
|
8,4,2,6
|
9
|
1
|
9
|
1
|
1
|
9,1
|
0
|
0
|
0
|
0
|
0
|
0
|
У цій таблиці наведено останні цифри натуральних чисел, квадратів, кубів, четвертих степенів і так далі. Використовуємо цю таблицю для розв’язування задач.
Задача 1. Знайти остачу від ділення квадрата цілого числа на 5.
Розв’язання:
Квадрати натуральних чисел закінчуються цифрами: 0; 1; 4; 5; 6; 9.(колонка 2) то при їх діленні на 5 одержуємо 0, 1 або 4.
Задача 2. Чи може число виду 1k+5m+6n, де k, m, n – довільні натуральні числа, бути довільним квадратом.
Розв’язання: Кожний доданок закінчується відповідно цифрами: 1, 5 і 6 (колонка 6) і тому їх сума закінчується цифрою 2, а таке число не може бути точним квадратом.
Задача 3. Довести, що число 5353- 3333 ділиться на 10.
Розв’язання: При виділенні показників степенів 53 і 33 на 4 в остачі одержуємо в кожному випадку 1. Отже, остання цифра числа 5553 така сама, як числа 3333, бо534∙13+1 і 334∙8+1, отже, остання цифра різниці 0, і ця різниця ділиться на 10.
Задача 4. Які остачі можуть мати точні квадрати при діленні на 3?
Відповідь: 0; 1; (3k±1)2=9k2±6k+1. (3k)2=9k.
Задача 5. Які остачі не можуть мати точні квадрати при діленні на 4?
(2k)2=4k2
(2k+1)2=4k2+4k+1
Відповідь: 2; 3.
Задача 6. Які остачі не можуть мати точні квадрати при діленні на 5?
Відповідь:2 і 3. (5k)2=25k2+0
(5k±1)2=25k2±10k+1
(5k±2)2=25k2±20k+4
Задача 7. Довести, що при будь-якому цілому n число n(n-3)(n2-3n+14) ділиться на 24?
Доведення:
n (n-3)(n2-n-2n+2+12)=n(n-3)(n(n-1)-2(n-1)+12)=n(n-3)(n-1)(n-2)+12n(n-3). Це число ділиться на 24, бо:
1. n(n-1)(n-2)(n-3) ділиться на 3 і 8 Þділиться на 24.
2. 12n(n-3) ділиться на 12 і 2, отже, ділиться на 24.
3. n (n-3)(n2-n-2n+2+12) ділиться на 2
Властивості квадратних лишків
Теорема 1. Завжди знайдеться натуральний дільник n, більшого 1, для довільного степеня натурального числа mk, який при ділення степеня на цей дільник n дає остачу 1, (або завжди можна знайти такі натуральні числа, що (mk– 1):n – натуральне число).
Тобто рівняння з двома невідомими завжди має розв’язки в натуральних числах
mk - 1º0(mod m-1).
Теорема 2. Завжди знайдеться натуральний дільник n, більший 5, для довільного квадрату натурального числа, який при ділення квадрата на цей дільник дає остачу 4.
Тобто, рівняння з двома невідомими завжди має розв’язки в натуральних числах
m2 º4(mod m+2) або m2 º4(mod m-2) .
Теорема 3. Завжди знайдеться такий натуральний дільник n для довільного квадрату натурального числа, який при ділення на цей натуральний дільник дає остачу 0.
Тобто рівняння з двома невідомими m i n завжди має розв’язки в натуральних числах
m2 º 0(mod n).
Теорема 4. Завжди знайдеться такий натуральний дільник n, більший 9, для довільного квадрату натурального числа, який при ділення на цей натуральний дільник n дає остачу 0.
Тобто рівняння з двома невідомими завжди має розв’язки в натуральних числах
m2 º9(mod n).
Тобто рівняння з двома невідомими m i n завжди має розв’язки в натуральних числах
m2 º9(mod m+3) або m2 º9(mod m-3).
Розглянемо декілька прикладів.
Задача. Чи існують чотири натуральних числа, що йдуть підряд, кожне з яких можна подати у вигляді суми двох квадратів?
Розв'язання.
Ні, не існують. Розглянемо остачі при діленні на 4. Квадрат може дати остачу 0 або 1, сума двох квадратів - 0, 1 або 2. серед чотирьох підряд чисел знайдеться таке, що має остачу 3. Воно на суму двох квадратів не розкладається.
Задача. Знайти всі такі р, що числа р, р + 10 та р + 14 прості.
Розв'язання.
Єдина відповідь p=3. Якщо p не ділиться на 3, то при p=3k + 1 число p+14 ділиться на 3, при p=3k+2 число p+10 ділиться на 3.
Задачі для самостійного осмислення
1. Рівняння з двома невідомими
m2 º 3(mod n).
має розв’язки в цифрах тільки один розв’язок m = 3, n = 6.
(Умова задачі на це рівняння. Знайти двоцифрове число, у якого квадрат цифри десятків при діленні на цифру одиниць дає остачу, що дорівнює половині цифри одиниць. Відповідь: 36.)
2. Рівняння з двома невідомими
m2 º2(mod n).
має розв’язки в цифрах тільки два розв’язки: m = 3, n = 7. m = 4, n = 7.
(Умова задачі на це рівняння. Знайти двоцифрові число, у яких квадрат цифри десятків при діленні на цифру одиниць дає остачу 2. Відповідь: 37 та 47.)
3. Чи існує магічний квадрат 3х3 , складений з натуральних чисел так, щоб виконувалася умова на парність чисел? (У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).
2n
|
2k-1
|
2r
|
2d-1
|
2t-1
|
2m-1
|
2c
|
2a-1
|
2k
|
Відповідь: існує, це магічний квадрат 3х3, з цифр 1, 2, 3, 4, 5, 6, 7, 8, 9.
4. Чи існує магічний квадрат 3х3, складений з натуральних чисел так, щоб виконувалася умова на парність чисел?(У магічного квадрату суми чисел по двох діагоналях, трьох вертикалях та трьох горизонталях рівні).
2n
|
2k-1
|
2r
|
2d-1
|
2t
|
2m-1
|
2c
|
2a-1
|
2k
|
Відповідь: не існує.
4.Чи існує така цифра, більша 1, яка ділиться на число вигляду m2 – 8. Відповідь: не існує.
5. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 5. Відповідь: 58, 56.
6. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 12, 32, 52, 72, 92. 23, 53, 83, 34, 74, 45, 56, 57, 78, 29, 89, 59.
7. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків. Відповідь: 12, 23, 34, 45, 56, 67, 78, 89.
8. (Теорема: m3 = m(mod m +1) та m3 = m(mod m -1), де m >1 )Доведіть, що всі двоцифрові числа, у яких цифри розташовані послідовно у порядку зростання, володіють такою властивістю: «куб цифри десятків при діленні на цифру одиниць, дає остачу, що дорівнює цифрі десятків.»
9. Знайти усі двоцифрові числа, у яких куб цифри десятків ділиться на цифру одиниць без остачі. Відповідь: 22, 42, 62, 82, 33, 44, 63, 93, 84, 64, 55, 66, 77, 88, 28, 48, 68,39, 69, 99.
10. Знайти двоцифрові числа, у яких куб цифри десятків при діленні на цифру одиниць, дає остачу 6, що дорівнює цифрі одиниць, зменшеній на 1. Відповідь: 57, 67.
Теорема про остачі
Відмітимо спочатку, що для будь-яких натуральних чисел а і b послідовності а,а2, а3, а4, ..., аn, ... остачі від ділення цих чисел на b будуть періодично повторюватись, починаючи з деякого місця. Адже за принципом Діріхле в нескінченній послідовності остач, які дають числа аn при діленні на b, обов'язково знайдуться дві однакові остачі. А якщо аk та as дають однакові остачі, то однаковими будуть остачі чисел аk+1 та аs+1, аk+2 та аs+2 і т.д. І якщо ми знайдемо закон періодичності остач в послідовності а, а2, а3, а4, ..., аn, ... , то легко зможемо вказати остачу для будь-якого числа аn.
Якщо остача від ділення числа а на b дорівнює с, то остача від ділення числа аn на b дорівнює остачі від ділення числа сn на b.
Приклад 1. 13 : 5 = 2 (ост. 3), тоді 13n :5 дає таку саму остачу, як і 3n: 5.
Розв'язання.
1) n = 2, 132:5 = 169:5 = 33 (ост. 4) і 32:5 = 9:5 = 1 (ост. 4);
2) n = 3, 133:5 = 2197:5 = 439 (ост. 2) і 33:5 = 27:5 = 5 (ост. 2);
3) n = 4, 134:5 = 28 561:5 = 5712 (ост. 1) і 34:5 = 81:5 = 16(ост. 1);
4) n = 5, 135:5 = 371 293:5 = 74 258 (ост. 3) і 35:5 = 243:5 = 48 (ост. 3).
Приклад 2. Знайти остачу від ділення числа 2222n на 7.
Розв'язання.
1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).
2) Остача від ділення 2222n на 7 така сама, як остача від ділення 34 на 7, тобто 4, бо
34:7 = 81:7 = 11 (ост. 4).
Відповідь. 4.
Задача 1. Знайти остачу від ділення числа 22225555 на 7.
Розв'язання.
1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).
Остача від ділення 22225555 на 7 така сама, як остача від ділення 35555 на 7.
Знайдемо остачі від ділення 3n на 7 для різних значень n:
n=1, 31:7 = 3:7 = 0 (ост. 3);
n = 2, 32:7 = 9:7 = 1 (ост. 2);
n = 3, 33:7 = 27:7 = 3 (ост. 6);
n = 4, 34:7 = 81:7 = 11 (ост. 4);
n = 5, 35:7 = 243:7 = 34 (ост. 5);
n = 6, 36:7 = 729:7 = 104 (ост. 1);
n = 7, 37:7 = 2187:7 = 312 (ост. 3).
Цикл дорівнює 6.
4) Знайдемо кількість повних циклів у числі 5555. 5555 : 6 = 925 (ост. 5).
925 повних циклів відкидаємо.
Отже, остача відділення 35555 на 7 така сама, як від ділення 35 на 7, тобто 5.
Отже, і остача від ділення 22225555 на 7 дорівнює 5.
Відповідь. 5.
Задача 2. Знайти остачу від ділення числа 55552222 на 7.
Розв'язання.
1) Знайдемо остачу від ділення 5555 на 7:
5555 : 7 = 793 (ост. 4).
Остача від ділення 55552222 на 7 така сама, як остача від ділення 42222 на 7.
Знайдемо остачі від ділення 4n на 7 для різних значень n:
n = 1, 41:7 = 4:7 = 0 (ост. 4);
n = 2, 42:7 = 16:7 = 2 (ост. 2);
n = 3, 43:7 = 64:7 = 9 (ост.1);
n = 4, 44:7 = 256:7 = 36 (ост. 4).
Цикл дорівнює 3.
2) Знайдемо кількість повних циклів у числі 2222.
2222 : 3 = 740 (ост. 2).
740 повних циклів відкидаємо.
Отже, остача від ділення 42222 на 7 така сама, як і від ділення 42 на 7, тобто 2.
Отже, і остача відділення 55552222 на 7 дорівнює 2.
Відповідь. 2.
Задача 3. Довести, що (22225555+55552222) ділиться на 7 без остачі.
Доведення.
Оскільки 22225555 при діленні на 7 дає остачу 5, а 55552222 при діленні на 7 дає остачу 2, а сума цих остач 5+2 = 7 ділиться на 7, то (22225555 +55552222) ділиться на 7 без остачі, що і треба було довести.
Задача 4. Знайти остачу від ділення числа 7 2003 на 10.
Розв'язання.
1) Знайдемо остачу від ділення 7 на 10: 7: 10 = 0 (ост. 7).
2)Знайдемо остачі від ділення 7n на 10 для різних значень n:
n = 1, 71:10 = 7:10 = 0 (ост. 7);
n = 2, 72:10 = 49:10 = 4 (ост. 9);
n = 3, 73:10 = 343:10 = 34 (ост. 3);
n = 4, 74:10 = 2401:10 = 240(ост. 1);
n = 5, 75 : 10 = 16 807:10 = 1680 (ост. 7).
Цикл дорівнює 4.
3)Знайдемо кількість повних циклів у числі 2003.
2003 : 4 = 500 (ост. 3).
4)500 повних циклів відкидаємо. Отже, остача від ділення 72003 на 10 така сама, як остача від ділення 73 на 10 , тобто 3.
Відповідь. 3.
5. Якою цифрою закінчується число 72003 ?
Розв'язання.
Остача відділення числа 72003 на 10 є останньою цифрою цього числа. Тобто число 72003 закінчується цифрою 3.
Відповідь. 3.
Самостійно виконайте дві наступні вправи.
6.Знайти остачу від ділення числа 20062007 на 3.
7. Якою цифрою закінчується 192008 ?
Задачі для самостійного осмислення
б) Вираз х + 2 ділиться без остачі на 3. Як записати це твердження за допомогою конгруенції? Знайти множину значень х.
б) Вираз 4х + 3 ділиться з остачею 2 на число 5. Як це записати за допомогою конгруенції? Знайти множину значень х.
б) Вираз 5х - 1 ділиться з остачею 3 на число 4. Як це записати за допомогою конгруенції? Знайти множину значень х.
б) Вираз а +2 ділиться без остачі на 3. Як записати це твердження за допомогою конгруенції?
б) Які з чисел 46, 37, 16, -17, -16 конгруентні 7 за модулем 2, 3, 5, 9.
6. Показати, що числа виду 8k+1, де k=0, 1, 2, ... конгруентні між собою за модулем 8.
7. Довести, що квадрат будь-якого непарного числа конгруентний
з одиницею за модулем 8.
з одиницею за модулем 8.
8. Показати, що при n непарному, тобто n = 2k±1, число n3
конгруентне 6k+1 за модулем 4.
конгруентне 6k+1 за модулем 4.
9. Довести, що якщо 50а+8b+с º 0 (mod 21), то а+b+8с º 0(mod 21).
10. Перевірити конгруенцію 830 º 34 (mod 55).
11. Перевірити конгруенцію 521º 27 (mod 77).
12. З яким найменшим натуральним числом конгруентне числоN=8∙22∙1212∙17∙23 за модулем 9?
13.Чи вірно, що число 8754 конгруентне 4578 за модулем 9?
14. Чи вірно, що число 5647 конгруентне 22 за модулем 9?
15. Чи вірно, що m3-m+7 конгруентне 7 за модулем 6?
16. Чи вірно, що (2+7)5 = 25+75 (mod 5)?
Комментариев нет:
Отправить комментарий