Поняття відносини подільності

Визначення.Число а ділиться на число тоді і тільки тоді, коли існує таке число q, що а = в × q . а в ( q N 0) [а = вq].

Позначають: а в. Читають: «число а кратно числу в», «число в – дільник числа а», «а кратно».

Рівність а = вq називають формулою кратності числа а числу ст.

Число а, кратне 2, називають парним. Загальний вигляд парного числа: а = 2n, n N0.

Число, кратне 3, має формулу: а = 3n, n N 0 .

Визначення.Відношення ділимості на множині N 0 N містить ті й ті пари чисел (а, в), у яких перша координата кратна другий. Позначають: «».

« » = ((а, в) | (а, в) N 0 N а в).

Якщо відношення ділимості позначити, тоN 0 N = ((а, в) | (а, в) N 0 N а = вq).

Теорема.Дільник цього числа а не перевищує цього числа, тобто, якщо а в а.

Доведення. Оскільки а, то (q N 0) [а = вq] а – в=вq-в=в(q – 1), тому що q N q 1.

Тоді (q – 1) 0 в а. З визначення відношення ділимості та рівності а = 1 × а, випливає, що 1 є дільником для будь-якого натурального числа.

Слідство. Безліч дільників цього числа звичайно.

Наприклад, дільники числа 18 є кінцева множина: (1, 2, 3, 6, 9, 18).

Властивості відношення подільності

1. Відношення ділимості рефлексивно, тобто будь-яке натуральне число ділиться саме на себе: (а N) [(а, а)], тобто а: а = 1.

Доведення. (а N) [а = а × 1] щодо визначення відношення ділимості а: а.

2. Відношення ділимості антисиметрично, тобто для різних чисел а і з того, що а, слід, що в не кратно а. (а, в N 0 N) [а в а в].

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

Нерівності в а в істини тільки в тому випадку, якщо а = в. дійшли суперечності з умовою. Отже, припущення, що а Л. Таким чином, відношення ділимості антисиметричне.

3. Відношення подільності транзитивне. (А, в, з N 0 N) [а в в с а с].

Доведення. Якщо а (q N) [а = вq] (1) З того, що в с (t N) [в = сt] (2)

Підставимо = сt у рівність (1), отримаємо: а = (сt)q = c(tq), t,q N tq N tq = р а = ср, р N. А це означає, що а с.

Ознаки подільності. Подільність суми, різниці, твори

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

Теорема(Ознака подільності суми). Якщо числа а і ділиться на число n, то їх сума ділиться на це число, (а, в, n N 0 N) [а n n (а + в) n].

Доведення. З того, що а n в n (за визначенням відношення ділимості)

а = nq 1 (1), q 1 N. в = nq 2 (2), q 2 N. Перетворимо суму (а + в) до виду:

а + = nq 1 + nq 2 = n (q 1 + q 2) = nq, q = q 1 + q 2 . а + = nq.

Отже, щодо визначення відношення ділимості, що (а + в) n.

Теорема(Ознака подільності різниці). Якщо числа а і в діляться на число n і а в, то їхня різниця а - ділиться на число n, тобто

(а, в, n N 0 N) [а n в n а (а - в) n].

Теорема(Ознака ділимості твору). Якщо один із множників добутку ділиться на число n, то і весь добуток поділяється на число n.

(а, в, n N 0 N) [а n (ав) n].

Доведення. З того що а n а = nq (1). Помножимо обидві частини рівності (1) на N, отримаємо: ав = nqв (за асоціативністю множення) ав = n(qв) = nt, де t = qв ав = nt. А це означає, що ав n (за визначенням відношення ділимості). Таким чином, для ділимості твору на число достатньо, щоб на дане число ділився хоча б один із множників цього твору.

Теорема.Якщо у творі ав множник ділиться на натуральне число m, а множник ділиться на натуральне число n, то ав ділиться на mn.

(а, в, m, n N) [а m в n ав mn].

Доведення. З того, що m а = mq 1 , q 1 N; в n = nq 2 , q 2 N

ав = mq 1 × nq 2 = mn(q 1 × q 2) = mnq, q 1 × q 2 = q N. ав = mnq ав mn.

Теорема(Ознака ділимості на 2). Для того щоб число х ділилося на 2 необхідно і достатньо, щоб його десятковий запис закінчувався однією з цифр: 0, 2, 4, 6, 8.

Доведення. Нехай число х записано в десятковій системі числення, тобто:

х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 де а n , a n –1 , …, а 1 – цифри, що приймають значення 0, 1, 2, 3, 4 , 5, 6, 7, 8, 9 та а n 0, а 0 – приймає значення 0, 2, 4, 6, 8.

Доведемо, що число х 2. Оскільки 10 2, то будь-який ступінь числа 10 2. Десятковий запис числа х подаємо у вигляді: х = (а n 10 n + a n –1 10 n –1 + …+a 1 10) + a 0

I доданок II доданок

У цій сумі перший доданок за ознакою ділимості суми поділяється на 2. Другий доданок а 02 (за умовою). Отже, за ознакою подільності суми число х ділиться на 2.

Назад, якщо число х ділиться на 2, його десятковий запис закінчується цифрою 0, 2, 4, 6, 8.

Запишемо число х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 у вигляді: а 0 = х – (а n 10 n + a n –1 10 n –1 + …+a 1 10).

У цій різниці число х 2 (за умовою), яке віднімається (а n 10 n + a n –1 10 n –1 + …+a 1 10) 2 (за ознакою подільності суми). Отже, за теоремою про розподіл різниці а 0 2. Щоб однозначне число а 0 ділилося на 2, воно має приймати значення 0, 2, 4, 6, 8.

Ознака ділимості на 2.На 2 діляться ті й ті числа, у розряді одиниць яких міститься число, що ділиться на 2 чи 2 діляться ті й ті числа, десятковий запис яких закінчується однієї з цифр 0, 2, 4, 6, 8.

Теорема(Ознака ділимості на 5). Для того щоб число х ділилося на 5, необхідно і достатньо, щоб його десятковий запис закінчувався цифрою 0 або 5.

Лемма. (n N) .

Доведення. Оскільки 100 = 4 × 25, то за ознакою подільності твору

100 4. Тоді ( n N n > 1) 10 n = 100 × 10 n–2 та за ознакою подільності твору 10 n 4.

Теорема(Ознака ділимості на 4). Натуральне число х ділиться на 4 тоді і лише тоді, коли дві останні цифри його десяткового запису утворюють двозначне число, що ділиться на 4.

Нехай х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 та нехай десятковий запис двох останніх цифр a 1 10 + a 0 виражає число , яке ділиться на 4.

Доведення. Представимо число х як суми двох доданків:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0),

I доданок II доданок

де перший доданок, за доведеною вище Лемме, ділиться на 4, другий доданок ділиться на 4 за умовою. Отже, згідно з ознакою подільності суми на число число х ділиться на 4.

Назад, якщо число х 4, то двозначне число, утворене останніми цифрами його десяткового запису, ділиться на 4.

За умовою х 4. Доведемо, що (а 110 + а 0) 4.

Доведення. Десятковий запис числа х має вигляд:

х = а n 10 n + a n –1 10 n –1 + …+а 2 10 2 + a 1 10 + a 0 , представимо число х у вигляді суми двох доданків:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0) і запишемо рівність у вигляді:

х – (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) = а 1 10 + а 0 де х 4 (а n 10 n + a n –1 10 n –1 + …+ a 2 10 2) 4 (по лемі).

Отже, за ознакою подільності різниці а 1 10 + а 0 4. вираз а 1 10 + а 0 = є запис двозначного числа, утвореного останніми цифрами запису числа х.

Ознака ділимості на 4.На 4 діляться ті й тільки ті числа, останні дві цифри десяткового запису яких утворюють число, що ділиться на 4.

Теорема.Щоб число х ділилося на 25 необхідно і достатньо, щоб на 25 ділилося двозначне число, утворене останніми двома цифрами десяткового запису числа х.

Доводиться аналогічно.

Ознака ділимості на 25.На 25 діляться ті й ті числа, які мають дві останні цифри у записи числа 00, 25, 50, 75.

Лемма.(n N) [(10 n - 1) 9].

Доведемо методом математичної індукції.

1. Перевіримо справедливість затвердження для n = 1,І 3

Ознака ділимості на 3.На 3 діляться лише ті числа, сума цифр яких ділиться на 3.

Визначення.Нехай дані натуральні числа а і b. Говорять, що число а ділиться на число b, якщо є таке натуральне число q, що а = bq.

У цьому випадку число b називають дільником числа а , а число а - кратним числа b.

Наприклад, 24 ділиться на 8, тому що існує таке q = 3 що 24 = 8×3. Можна сказати інакше: 8 це дільник числа 24, а 24 є кратне числа 8.

У тому випадку, коли аділиться на b,пишуть: а M b. Цей запис часто читають і так: «а кратно b».

Зауважимо, що поняття «дільник цього числа» слід відрізняти від поняття «ділитель», що означає те число, на яке ділять. Наприклад, якщо 18 ділять на 5, то число 5 - дільник, але 5 не є дільником числа 18. Якщо 18 ділять на 6, то в цьому випадку поняття дільник і дільник даного числа збігаються.

З визначення відношення ділимості та рівності a = 1 × а,справедливого для будь-якого натурального а,випливає, що 1 є дільником будь-якого натурального числа.

З'ясуємо, скільки взагалі дільників може бути у натурального числа а.Спочатку розглянемо таку теорему.

Теорема 1. Дільник b даного числа а не перевищує цього числа, тобто якщо M b, то b £ а.

Доведення.Оскільки а M b, існує таке qÎ N, що а = bq і, отже, а - b = bq - b = b ×(q - 1). Оскільки qÎ N, то q ³ 1. . Тоді b × (q - 1) ³ 0 і, отже, і b а.

З цієї теореми випливає, що безліч дільників цього числа звичайно. Назвемо, наприклад, усі дільники числа 36. Вони утворюють кінцеву множину (1,2,3,4,6,9,12,18,36).

Залежно від числа дільників серед натуральних чисел розрізняють прості та складові числа.

Визначення.Простим числом називається таке натуральне число, більше 1, яке має лише два дільники - одиницю і саме це число.

Наприклад, 13 - просте, оскільки у нього лише два дільники: 1 і 13.

Визначення.Складовим числом називається таке натуральне число, яке має понад два дільники.

Так число 4 складене, має три дільника: 1, 2 і 4. Число 1 не є ні простим, ні складовим числом у зв'язку з тим, що воно має тільки один дільник.

Чисел, кратних даному числу, можна назвати як завгодно багато, - їх безліч. Так, числа, кратні 4, утворюють нескінченний ряд: 4, 8, 12, 16, 20, 24, ... і всі вони можуть бути отримані за формулою а = 4q, де q приймає значення 1, 2, 3,. .. .

Нам відомо, що відношення подільності на безлічі N має ряд властивостей, зокрема, воно рефлексивне, антисиметричне та транзитивне. Тепер, маючи визначення відношення ділимості, ми можемо довести ці та інші його властивості.

Теорема 2. Ставлення ділимості рефлексивно, тобто. будь-яке натуральне число ділиться саме на себе.

Доведення.Для будь-якого натурального асправедлива рівність а=а× 1. Оскільки 1 Î N то, за визначенням відношення ділимості, аMа.

Теорема 3. Ставлення ділимості антисиметрично, тобто. якщо а M b і а b, то .

Доведення.Припустимо неприємне, т. е. що bMа. Але тоді а?b, згідно з теоремою, розглянутою вище.

За умовою а M b та а ¹ b. Тоді, за тією самою теоремою, b £ а.

Нерівності а £ b і b £ а. будуть справедливі лише тоді, коли а = b, що суперечить умові теореми. Отже, наше припущення є невірним і теорема доведена.

Теорема 4. Ставлення подільності транзитивно, тобто. якщо а M b та b M с, то а M с.

Доведення.Так як а M b, q,що а = b q,а так як bM с,то існує таке натуральне число р, що b = пор.Але тоді маємо: а = b q = (СР)q = с(рq).Число рq -натуральне. Значить, за визначенням відношення подільності, а. M с.

Теорема 5(Ознака подільності суми). Якщо кожне з натуральних чисел а 1, а 2 ,…а поділяється на натуральне число b, то їх сума а 1 + а 2 + … + а поділяється на це число.

Наприклад, не роблячи обчислень, можна сказати, що сума 175 + 360 +915 ділиться на 5, тому що на 5 ділиться кожне доданок цієї суми.

Теорема 6(Ознака подільності різниці). Якщо числа а 1 і а 2 діляться на b і а 1 ³ а 2 , їх різниця а 1 - а 2 ділиться на b.

Теорема 7(Ознака ділимості твору). Якщо число ділиться на b, то добуток виду ах, де х е N. ділиться на b.

З теореми випливає, що якщо один із множників добутку ділиться на натуральне число b, то і весь твір поділяється на b.

Наприклад, Добуток 24×976×305 ділиться на 12, так як на 12 ділиться множник 24.

Розглянемо ще три теореми, пов'язані з ділимістю суми та твори, які часто використовуються під час вирішення завдань на ділимість.

Теорема 8. Якщо в сумі один доданок не ділиться на число b, а решта доданків поділяється на число b, то вся сума на число b не ділиться.

Наприклад,сума 34 + 125 + 376 + 1024 на 2 не ділиться, тому що 34:2,376: 2,124: 2, але 125 не ділиться на 2.

Теорема 9. Якщо у творі аb множник а ділиться на натуральне число т, а множник b ділиться на натуральне число, то а b ділиться на тп.

Справедливість цього твердження випливає з теореми про подільність твору.

Теорема 10. Якщо добуток ас поділяється на добуток bс, причому с - натуральне число, то і ділиться на b.

2. Прості та складові числа

Прості числа грають велику роль математиці - сутнісно є «цеглинами», у тому числі будуються складові числа.

Це стверджується в теоремі, яка називається основною теоремою арифметики натуральних чисел, яка наводиться без доказу.

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

Наприклад, запис 110 = 2×5×11 є подання числа 110 у вигляді добутку простих множників або розкладання його на прості множники.

Два розкладання числа на прості множники вважають однаковими, якщо вони відрізняються один від одного лише порядком множників. Тому подання числа 110 у вигляді твору 2×5×11 або твору 5×2×11 є, по суті, те саме розкладання числа 110 на прості множники.

Розкладаючи числа на прості множники, використовують ознаки подільності на 2, 3, 5 та ін. Нагадаємо один із способів запису розкладання чисел на прості множники. Розкладемо, наприклад, на множники число 90. Число 90 ділиться на 2. Значить, 2 є один із простих множників у розкладанні числа 90. Розділимо 90 на 2. 45 ділимо на просте число 3, отримуємо 15. Ділимо 15 на 3, отримуємо 5. Число 5 - просте, при розподілі його на 5 отримуємо 1. Розкладання на множники закінчено.

При розкладанні числа на прості множники добуток однакових множників репрезентують у вигляді ступеня: 90=2×3 2 ×5; 60 = 2 2 × 3 × 5; 72 = 2 3 × 3 2 . Таке розкладання числа на прості множники називають канонічним.

Грецький математик - Евклід довів, що безліч простих чисел нескінченно.

Справді, припустимо, що безліч простих чисел кінцева і вичерпується числами 2, 3, 5, 7, ..., р, де p – найбільше просте число. Перемножимо всі прості числа та їх добуток позначимо через а. Додамо до цього числа 1. Яким буде отримане число а + 1 – простим чи складовим?

Простим число а+1 бути не може, тому що воно більше за найбільше просте число, а за припущенням таких простих чисел не існує. Але складним воно теж бути не може: якщо а + 1 складове, воно повинно мати хоча б один простий дільник q. Оскільки число а = 2×3×5 ×...×р також ділиться цього просте число q, те й різницю (а + 1) - а, тобто. число 1 ділиться на q, що неможливо.

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

3. Ознаки подільності

Розглянуті властивості відносини ділимості дозволяють довести відомі ознаки ділимості чисел, записаних у десятковій системі числення, на 2, 3, 4, 5, 9.

Ознаки ділимості дозволяють встановити по запису числа чи ділиться воно інше, не виконуючи поділу.

Теорема 11 (Ознака ділимості на 2). Для того, щоб число х ділилося на 2, необхідно і достатньо, щоб його десятковий запис закінчувався однією з цифр 0, 2, 4, 6, 8.

Доведення.Нехай число х записано у десятковій системі числення, тобто. х=а п 10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 де а п,а п-1 , …, а 1 приймають значення 0, 1,2, 3, 4, 5, 6, 7, 8, 9, а п 0 і а 0 приймає значення 0,2,4,6,8. Доведемо, що тоді х M2.

Так як 10M2, то 10 2 M2, 10 3 M2, ..., 10 п M2 і, отже, а п 10 п + а п-1 × 10 п-1 + ... + а 1 × 10M2. За умовою а 0 теж ділиться на 2, і тому число х можна розглядати як суму двох доданків, кожне з яких ділиться на 2. Отже, згідно з ознакою поділення суми, число х ділиться на 2.

Доведемо протилежне: якщо число х ділиться на 2, його десятковий запис закінчується однією з цифр 0, 2, 4, 6, 8.

Запишемо рівність х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 у такому вигляді: а 0 =х-(а п ×10 п +а п-1 × 10 п-1 + ... + а 1 × 10). Але тоді, за теоремою про розподіл різниці, а 0 M2, оскільки хM2 і (а п × 10 п + а п-1 × 10 п-1 + ... + а 1 × 10) M2. Щоб однозначне число а 0 ділилося на 2, воно має набувати значень 0, 2, 4, 6, 8.

Теорема 12 (Ознака ділимості на 5). Для того, щоб число х ділилося на 5, необхідно і достатньо, щоб його десятковий запис закінчувався цифрою 0 або 5.

Доказ цієї ознаки аналогічний доказу ознаки подільності на 2.

Теорема 13 (Ознака ділимості на 4). Для того, щоб число х ділилося на 4, необхідно і достатньо, щоб на 4 ділилося двозначне число, утворене останніми двома цифрами десяткового запису числа х.

Доведення. Нехай число х записано у десятковій системі числення, тобто. х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 і дві останні цифри цього запису утворюють число, яке ділиться на 4. Доведемо, що тоді хM4.

Так як 100M4, то (а п × 10 п + а п-1 × 10 п-1 + ... + а 2 × 10 2) M4. За умовою, а 1 ×10+а 0 (це і є запис двозначного числа) також поділяється на 4. Тому число х можна розглядати як суму двох доданків, кожне з яких поділяється на 4. Отже, відповідно до ознаки поділення суми, і саме число х ділиться на 4.

Доведемо протилежне, тобто. якщо число х ділиться на 4, то двозначне число, утворене останніми цифрами його десяткового запису, також поділяється на 4.

Запишемо рівність х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 у такому вигляді: а 1 ×10+а 0 =х-(а п ×10 п + а п-1 × 10 п-1 + ... + а 2 × 10 2). Так як хM4 і (а п × 10 п + а п-1 × 10 п-1 + ... + а 2 × 10 2), то за теоремою про подільність різниці (а 1 × 10 + а 0) M4. Але вираз а 1×10+а 0 є запис двозначного числа, утвореного останніми цифрами запису числа х.

Наприклад, Число 157872 ділиться на 4, так як останні дві цифри в його записі утворюють число 72, яке ділиться на 4. Число 987641 не ділиться на 4, так як останні дві цифри в його записі утворюють число 41, яке не ділиться на 4.

Теорема 14 (Ознака подільності на 9). Щоб число х ділилося на 9, необхідно і достатньо, щоб сума цифр його десяткового запису ділилася на 9.

Доведення.

Доведемо спочатку, що числа виду 10 п -1 поділяються на 9. Дійсно,

10 п -1=(9×10 п-1 +10 п-1)-1=(9×10 п-1 +9×10 п-2 +10 п–2)-1=(9×10 п- 1+9×10 п-2 +...+10)-1=

9×10 п-1+9×10 п-2+...+9. Кожне доданок отриманої суми ділиться на 9, отже, число 10 п -1 ділиться на 9.

Нехай число х=а п×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 та (а п +а п-1 +…+а 1 +а 0)M 9. Доведемо, що тоді хM9.

Перетворимо суму а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 , додавши та віднімаючи з неї вираз а п +а п-1 +…+а 1 +а 0 записавши результат у такому вигляді:

х=(а п ×10 п -а п)+(а п-1 ×10 п-1 -а п-1)+...+(а 1 ×10-а 1)+(а 0 -а 0 )+(а п +а п-1 +…+а 1 +а 0)= =а п (10 п-1 -1)+а п-1 (10 п-1 -1)+...+а 1 × (10 п-1 -1) + (а п + а п-1 + ... + а 1 + а 0).

В останній сумі кожне доданок ділиться на 9:

а п (10 п-1 - 1) M9, так як (10 п-1 -1) M9,

а п-1 (10 п-1-1) M9, так як (10 п-1 - 1) M9 і т.д.

(а п + а п-1 + ... + а 1 + а 0) M 9 за умовою.

Отже, хM9.

Доведемо протилежне, тобто. якщо хM9, то сума цифр його десяткового запису поділяється на 9.

Рівність х = а п × 10 п + а п-1 × 10 п-1 + ... + а 1 × 10 + а 0 запишемо в такому вигляді:

а п +а п-1 +…+а 1 +а 0 =х-(а п (10 п -1)+а п-1 (10 п–1 -1)+...+а 1 (10- 1)).

Так як у правій частині цієї рівності і зменшуване, і віднімається кратні 9, то по теоремі про розподіл різниці (а п + а п-1 + ... + а 1 + а 0) M9, тобто. сума цифр десяткового запису числа хділиться на 9, що потрібно було довести.

Наприклад,число 34578 ділиться на 9, оскільки сума його цифр, що дорівнює 27, ділиться на 9. Число 130542 не ділиться 9, оскільки сума його цифр, що дорівнює 15, не ділиться на 9.

Теорема 15(Ознака ділимості на 3). Щоб число х ділилося на 3, необхідно і достатньо, щоб сума цифр його десяткового запису ділилося на 3.

Доказ цього твердження аналогічний доказу ознаки подільності на 9.

Ми розглянули ознаки ділимості чисел на 2, 3, 4, 5, 9. Зі шкільного курсу математики відома ще низка інших, наприклад, на 10 і 25. Звичайно, цього недостатньо, щоб вирішувати питання ділимості. Існує загальна ознака ділимості для чисел, записаних у будь-якій позиційній системі числення, відкрита у XVII столітті французьким математиком Паскалем. Ми розглянемо його на випадок, коли основою системи числення є число 10.

Теорема 16 (ознака ділимості Паскаля). Число х = а п× 10 п + а п-1× 10 п -1 + ... + а 1× 10 + а 0 ділиться на число b тоді і лише тоді, коли на b ділиться сума а п× r п + а п-1× r п -1 + ... + а 1× r 1 + а 0 , де r 1 , r 2 , ..., r n - Залишки від розподілу на bрозрядних одиниць 10, 10 2 , ..., 10 n .

Використовуючи цю ознаку, виведемо, наприклад, відомий ознака ділимості на 3 у десятковій системі числення.

Знайдемо залишки від розподілу розрядних одиниць на 3:

10 =3×3+1(r 1 =1);

10 2 = 3×33 + 1 (r 2 = 1);

10 3 = 10 2 10 = (3 × 33 + 1) × (3 × 3 + 1) = 3q 3 + 1 (r 3 = 1).

З розглянутих випадків можна припустити, що ("n Î N) 10 n =3q n +1. Переконатися у істинності цього твердження можна, якщо скористатися методом математичної індукції.

Таким чином, доведено, що число ділиться на 3 і тоді, коли сума цифр його десяткового запису ділиться на 3.

Використовуючи ознаку ділимості Паскаля, можна довести наступну ознаку ділимості чисел на 11: для того, щоб число ділилося на 11, необхідно і достатньо, щоб різницю між сумою його цифр, що стоять на непарних місцях, і сумою цифр, що стоять на парних місцях, ділилася на 11. Зазвичай при знаходженні різниці з більшої кількості віднімають менше.

Наприклад,число 540309 ділиться на 11, тому що (4 + 3 + 9) - (5 + 0 + 0) = 11, а 11: 11. Число 236 не ділиться на 11, оскільки (2 + 6) - 3 = 5, але 5 не кратно 11.

4. Найменше загальне кратне та найбільший спільний дільник

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

Визначення.Загальним кратним натуральних чисел а і b називається число, яке кратне кожному з цих чисел.

Найменше з усіх загальних кратних чисел а і b називається найменшим загальним кратнимцих чисел.

Найменше загальне кратне чисел а та b умовимося позначати К(а, b). Наприклад, два числа 12 та 18 загальними кратними є: 36, 72, 108, 144, 180 і т.д. Число 36 - найменше загальне кратне чисел 12 та 18. Можна записати: К(12,18) = 36.

Для найменшого загального кратного справедливі такі твердження:

1. Найменше загальне кратне чисел а та b завжди існує і є єдиним.

2. Найменше загальне кратне чисел а і b не менше за більший з даних чисел, тобто. якщо а > b, то К(а, b) ³ а.

3. Будь-яке загальне кратне чисел а і b ділиться з їхньої найменше загальне кратне.

Визначення.Спільним дільником натуральних чисел а та b називається число, яке є дільником кожного з цих чисел.

Найбільше з усіх загальних дільників чисел а і b називається найбільшим спільним дільником даних чисел. Найбільший спільний дільник чисел а та b умовимося позначати D(а, b).

Наприкладдля чисел 12 і 18 загальними дільниками є числа: 1,2,3,6. Число 6 - найбільший загальний дільник чисел 12 та 18. Можна записати: D (12,8) = 6.

Число 1 є спільним дільником будь-яких двох натуральних чисел а та b. Якщо цих чисел немає інших спільних дільників, то D(а, b) = 1, а числа а і b називаються взаємно простими.

Наприклад,числа 14 і 15 – взаємно прості, тому що D (14, 15) = 1.

Для найбільшого спільного дільника справедливі такі твердження:

1. Найбільший спільний дільник чисел а і b завжди існує і єдиний.

2. Найбільший загальний дільник чисел а і b вбирається у меншого з даних чисел, тобто. якщо а< b, то D (а, b) £ а.

3. Найбільший спільний дільник чисел а та b ділиться на будь-який спільний дільник цих чисел.

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

До(а, b)×D(а,b)=а×b.

З цього твердження випливають такі наслідки:

а) Найменше загальне кратне двох взаємно простих чисел дорівнює добутку цих чисел, тобто D(а,b) = 1 ÞК(а,b)=а× b.

Наприклад,щоб знайти найменше загальне кратне чисел 14 та 15, достатньо їх перемножити, тому що D (14, 15) = 1.

б) Для того, щоб натуральне число а ділилося на добуток взаємно простих чисел m і n, необхідно і достатньо, щоб воно ділилося і на m, і на n.

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

Наприклад,оскільки 6=2 × 3 і D(2,3)=1, то отримуємо ознаку ділимості на 6: щоб натуральне число ділилося на 6, необхідно і достатньо, щоб воно ділилося на 2 і на 3.

Зауважимо, що цю ознаку можна застосовувати багаторазово. Сформулюємо, наприклад, ознаку ділимості на 60: для того, щоб число ділилося на 60, необхідно і достатньо, щоб воно ділилося і на 4, і на 15. У свою чергу, число ділитися на 15 тоді і тільки тоді, коли воно ділиться і на 3, і на 5. Узагальнюючи, отримуємо наступну ознаку ділимості на 60: щоб число ділилося на 60, необхідно і достатньо, щоб воно ділилося на 4, на 3 і на 5.

Визначення. Нехай дані натуральні числа а і b. Говорять, що число а ділиться на число b, якщо є таке натуральне число q, що a = bq.

У цьому випадку число b називають дільником числаа, а число а - кратним числа b.

Наприклад, 24 ділиться на 8, оскільки існує таке q = 3, що 24 = 8 · 3. Можна сказати інакше: 8 - це дільник числа 24, а 24 є кратне числа 8. У разі, коли а ділиться на b, пишуть: а: . b. Цей запис» «читають і так: «а кратно b». Зауважимо, що поняття «дільник цього числа» слід відрізняти від поняття «ділитель», що означає те число, на яке ділять. Наприклад, якщо 18 ділять на 5, то число 5 - дільник, але 5 не є дільником числа 18. Якщо 18 ділять 6, то в цьому випадку поняття дільник і дільник даного числа збігаються.

З визначення відношення ділимості і рівності а = 1 а, справедливого для будь-якого натурального а, випливає, що 1 є дільником будь-якого натурального числа.

З'ясуємо, скільки взагалі дільників може бути у натуральної кількості а. Спочатку розглянемо таку теорему.

Теорема 1. Дільник b цього числа а чи не перевищує цього числа, тобто. якщо

а: . b, то b< а.

Доведення. Оскільки: . b, існує таке q Є N,що a = bq u, значить, a-b = bq – b= b·(q - 1). Оскільки q Є N, то q≥ 1. Тоді b · (q - 1) ≥ 0 і, отже , b ≤ а.

З цієї теореми випливає, що безліч дільників цього числа звичайно. Назвемо, наприклад, усі дільники числа 36. утворюють кінцеву множину (1,2,3,4,6,9,12,18,36).

Залежно від числа дільників серед натуральних чисел розрізняють прості та складові числа.

Визначення. Простим числом називається таке натуральне число, яке має лише два дільники - одиницю і саме це число.

Наприклад, число 13 просте, оскільки, у нього тільки два дільники: 1 і 13.

Визначення. Складовим числом називається таке натуральне число, яке має понад два дільники.

Так число 4 складене, у нього три дільники: 1,2 та 4.

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

Чисел, кратних даному числу, можна назвати як завгодно багато, - їх безліч. Так, числа, кратні 4, утворюють нескінченний ряд: 4, 8, 12, 16, 20, 24, … і всі вони можуть бути отримані за формулою а = 4q, де q приймає значення 1, 2, 3,... .

Нам відомо, що відношення ділимості має ряд властивостей, зокрема, воно рефлексивне, антисиметричне та транзитивне. Тепер, маючи визначення відношення ділимості, ми можемо довести ці та інші його властивості.

Теорема 2. Ставлення ділимості рефлексивно, тобто. будь-яке натуральне число ділиться саме на себе.

Доведення. Для будь-якого натурального а справедлива рівність а = а·1. Так як 1 Є N, то за визначенням відношення ділимості, а: . а.

Теорема 3. Ставлення ділимості антисиметрично, тобто. якщо: . b та а ≠ b,

то b ⁞Η a.

Доведення. Припустимо неприємне, тобто. що b ⁞ a. Але тоді а ≤ b, згідно з теоремою, розглянутою вище.

За умовою та а ⁞ . b та а ≠ b. Тоді, за тією самою теоремою, b ≤ а.

Нерівності а ≤ b та b ≤ а будуть справедливі лише тоді, коли а = b, що суперечить умові теореми. Отже, наше припущення є невірним і теорема доведена.

Теорема 4. Ставлення подільності транзитивно, тобто. якщо а ⁞ b і b ⁞ с, то а ⁞ с.

Доведення. Оскільки: . b, існує таке натуральне число q, що a = bq, бо b ⁞ с, існує таке натуральне число р, що b = порівн. Але тоді маємо: a = bq = (cp)q = c(pq) - Число pq - натуральне. Значить, за визначенням відношення подільності,

а ⁞ с.

Теорема 5 (ознака подільності суми). Якщо кожне з натуральних чисел а 1 , а 2 , ..., а поділяється на натуральне число b, то їх сума a 1 + а 2 + ... + а n ділиться на це число.

Доведення. Оскільки 1 ⁞ b, існує таке натуральне число q 1 , що а 1 =bq 1 . Так як 2 ⁞ b, існує таке натуральне число q 2 , що а 2 = bq 2 . Продовжуючи міркування, отримаємо, якщо а n: . b, існує таке натуральне число q n , що а п = bq n . Ці рівності дозволяють перетворити суму а 1 + а 2 + ... + ап у суму виду bq 1 + bq 2 + ... + bq n . Винесемо за дужки загальний множник b, а натуральне число q 1 + q 2 + ... + q n, що вийшло в дужках, позначимо буквою q. Тоді a 1+ a 2 + ... + a n = b (q 1 + q 2 + ... + q n) = bq, тобто. сума а 1 + а 2 +… + а виявилася представленою у вигляді добутку числа b і деякого натурального числа q. А це означає, що сума а 1 + а 2 + ... + а ділиться на b, що і потрібно довести.

Наприклад, не роблячи обчислень, можна сказати, що 175 + 360 + 915 ділиться на 5, так як на 5 ділиться кожне доданок цієї суми.

Теорема 6 (ознака подільності різниці). Якщо числа а 1 і а 2 діляться на b і а 1 а 2 , то їх різниця а 1 - а 2 ділиться на b.

Доказ цієї теореми аналогічний доказу ознаки подільності суми.

Теорема 7 (ознака подільності твору). Якщо число а ділиться на b, то добуток виду ах, де х Є N, ділиться на b.

Доведення. Оскільки: . b, існує таке натуральне число q, що a= bq. Помножимо обидві частини цієї рівності на натуральне число x. Тоді ах=(bq)x, звідки виходячи з властивості асоціативності множення (bq)x = b(qx)і, отже, ax = b(qx), де qx - натуральне число. Відповідно до визначення відносини ділимості, ax: . b, що потрібно було довести.

З доведеної теореми випливає, що й один із множників твори ділиться на натуральне число b, те й усе твір ділиться на b. Наприклад, добуток 24 976 305 ділиться на 12, так як на 12 ділиться множник 24.

Доведення. Нехай s = а 1 + а г + ... + а п + "с і відомо, що а 1: B, а 2: B,

а 3: . b, … а n: . b, але з: . b. Доведемо, що тоді s: . b

Припустимо неприємне, тобто. Нехай s: . b. Перетворимо суму s на вигляд с = s- ( а 1 + а 2 +… + а n). Оскільки s: . b за припущенням, ( а 1 + а 2 +… + а n): . b згідно з ознакою ділимості суми, то за теоремою ділимості різниці з: .b

Прийшли протиріччя з тим, що дано. Отже, s: . b.

Наприклад, сума 34 + 125 + 376 + 1024 на 2 не ділиться, так 34: .2,376: .2,124: .2, але 125 не ділиться на 2.

Теорема 9 . Якщо у творі ab множник aділиться на натуральне число т, а множник b ділиться на натуральне число n, ab ділиться на mn.

Справедливість цього твердження випливає з теореми про подільність твору.

Теорема 10.Якщо твір асділиться на твір bс, причому с - натуральне число, те й аділиться на b.

Доведення. Оскільки ас ділиться на bc,то є таке натуральне число q, що ас = (bc)q, звідки ас = (bq)c і, отже, а = bq, тобто. а: .b.

Вправи

1. Поясніть, чому число 15 є дільником числа 60 та не є дільником числа 70.

2. Побудуйте граф відносини «бути дільником даного числа», заданого на множині Х = (2, 6, 12, 18, 24). Як відбито у цьому графі характеристики даного отношения?

3. Відомо, що число 24 - дільник числа 96, а число 96 - дільник числа 672. Доведіть, що число 24 дільник числа 672, не виконуючи поділу.

4. Запишіть безліч дільників числа.

а) 24; 6) 13; в 1.

5 .На множині X = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12) задано відношення «мати одне і те ж число дільників». Чи воно є ставленням еквівалентності?

6 .Побудуйте висновок, що доводить, що:

а) число 19 є простим;

б) число 22 є складовим.

7. Доведіть або спростуйте такі твердження:

а) Якщо сума двох доданків поділяється на деяке число, то й кожне доданок поділяється на це число.

б) Якщо один із доданків суми не ділиться на деяке число, то й сума не ділиться на це число.

в) Якщо жодна доданок не поділяється на деяке число, то сума не ділиться на це число.

г) Якщо один із складових суми ділиться на деяке число, а інше не ділиться на це число, то й сума не ділиться на це число.

8. Чи правильно, що:

а) а: . ти b: . n => ab: .mn

б) а: .п та b: .n => ab: .n;

в) ab: .n => а: .п чи b: .n.

Відношення ділимості та її властивості Визначення Нехай а і b N. Число а поділяється на число b, якщо існує таке натуральне число q, що а = bq а b q N , що а = bq У цьому випадку число b називають дільником числа а, а число а - кратним числа b 24 8, т. К. 3 N , Що 24 = 8 3

Розрізняють поняття «b дільник числа а» та «b – дільник» У виразі «25: 8» число 8 дільник (як компонент поділу), а у виразі «24: 8» число 8 дільник числа 24 Теорема 1 1 є дільником будь-якого натурального числа т. к. для а N а = 1 · а Теорема 2 Якщо а b, то b а

Доказ Оскільки а b, то q N, що а = bq а – b = bq – b = b · (q – 1). Оскільки а N, то q 1. Тоді b · (q - 1) 0, тобто різниця а - b 0 b а З Теореми 2 випливає: Безліч дільників даного числа а звичайно - всі дільники менше числа b Всі дільники числа 36 утворюють кінцеву множину (1, 2, 3, 4, 6, 9, 12, 18, 36)

Властивості відношення ділимості Теорема 3 (а N) а, тобто відношення ділимості рефлексивно Доказ (а N) а = а · 1. Так як 1 N ділимості, а а

Теорема 4 (а b і а b) b а, тобто відношення ділимості антисиметрично Доказ (від протилежного) Нехай невірно, що b а а b (за теоремою 2) За умовою а b і а b b а (за теоремою 2) Нерівності а b і b а будуть справедливими лише тоді, коли а = b, що суперечить умові теореми. Отже, наше припущення неправильне

Теорема 5 а b і b с а с, тобто відношення ділимості транзитивно Доказ А b q N, що а = bq Так як b с р N, що b = сра = bq = (ср)q = c( pq). Число pq N. Отже, за визначенням відношення ділимості, а з

Теорема 6 (ознака поділення суми) Якщо кожне з натуральних чисел а 1, а 2, . . . , аn ділиться на натуральне число b, то їх сума а 1 + а 2 +. . . + аn ділиться цього число Доказ Оскільки а 1 b, то q 1 N, що а 1= b q 1 Оскільки а 2 b, то q 2 N, що а 2= b q 2 ……………………. Оскільки аn b, то qn N, що аn= b qn

а 1+а 2+. . . + аn = b (q 1 + q 2 +. . . + qn) = bq q = q 1 + q 2 +. . . + qn, тобто q N тобто сума а 1 + а 2 +. . . + аn є добутком числа b і натурального числа q. Отже, сума а1+а2+. . . + аn ділиться на b Приклад Сума (175 + 360 + 915) 5, тому що 175 5 і 360 5 і 915 5

Теорема 7 (ознака ділимості різниці) Якщо а 1 b, а 2 b і а 1 > а 2, то (а 1 – а 2) b Доказ аналогічний доказу теореми 6

Теорема 8 (ознака ділимості твору) Якщо а b, то ах b, де х N Доказ Оскільки а b, то q N, що а = bq на х ах = (bq)x = b(qx), тобто. ах = b(qx), де qx N щодо визначення відношення ділимості ax b

З теореми 8 випливає, що якщо один із множників твору ділиться на натуральне число b, то і весь твір ділиться на b Приклад Твір (24 · 976 · 305) 12, тому що 24 12 Теорема 9 Якщо в сумі один доданок не ділиться на число b, а решта доданків діляться на число b, то вся сума на число b не ділиться

Приклад Сума (34 + 125 + 376 + 1024) 2, так як 34 2, 376 2, 124 2, але 125 2 Теорема 10 Якщо у творі ab множник ділиться на натуральне число m, а множник b ділиться на натуральне число n то ab ділиться на mn Доказ заснований на теоремі 8

Теорема 11 Якщо ас bс і з N, то а b Доказ Оскільки ас bс, то q N таке, що ас = (bc)q ас = (bq)c, отже, а = bq, тобто a b

Ознаки ділимості Теорема 12 (ознака ділимості на 2) Для того щоб число х ділилося на 2, необхідно і достатньо, щоб його десятковий запис закінчувався однією з цифр 0, 2, 4, 6, 8 Доказ 1) Нехай число х записано в десятковій системі числення: х = аn · 10 n + аn-1 · 10 n - 1 +. . . + а 1 · 10 + а 0 де аn, аn-1, . . . а 1 приймають значення 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, аn 0 і а 0 приймає значення 0, 2, 4, 6, 8

х = аn · 10 n + аn-1 · 10 n -1 +. . . + а 1 · 10 + а 0 = = (аn · 10 n-1 + аn-1 · 10 n -2+. . . + а 1) · 10 + а 0 ділиться на 2, тому що 10 2 а 0 теж ділиться на 2, тому що за умовою закінчується на 0, 2, 4, 6 або 8

2) Доведемо, що, якщо число х 2, то а 0 приймає значення 0, 2, 4, 6 або 8 х = аn · 10 n + аn-1 · 10 n -1 +. . . + а 1 · 10 + а 0 = х - (аn · 10 n + аn-1 · 10 n -1 +. . . + а 1 · 10) ділиться на 2, т. К. 10 2 Число х 2 за умовою а 0 2

Теорема 13 (ознака ділимості на 5) Для того щоб число х ділилося на 5, необхідно і достатньо, щоб його десятковий запис закінчувався цифрою 0 або 5 Доказ аналогічний до ознаки ділимості на 2 докази

Теорема 14 (ознака ділимості на 4) Для того, щоб число х ділилося на 4, необхідно і достатньо, щоб на 4 ділилося двозначне число, утворене останніми двома цифрами десяткового запису числа х Доказ 1) х = аn· 10 n+аn-1· 10 n -1+. . . а 2 102 + а 1 · 10 + а 0 = = (аn · 10 n-2 + аn-1 · 10 n -3 +. . . + а 2) · 102 + а 1 10 + а 0 ділиться на 4, т. до. 102 4 ділиться на 4 за умовою

2) Доведемо, що якщо число х 4, то (а 1 10 + а 0) утворює двозначне число, яке ділиться на 4 х = аn· 10 n + аn-1· 10 n -1+. . . + а 2 10 2 + а 1· 10 + а 0 = х – (аn· 10 n + аn-1· 10 n -1+. . . + а 2 10 2) ділиться на 4, тому що 102 4 Число х 4 за умовою (а 1 · 10 + а 0) 4

Приклад 1) Число 1 5 7 8 7 2 4 72 4 2) Число 9 8 7 6 4 1 4 41 4

Теорема 15 (ознака ділимості на 9) Для того, щоб число х ділилося на 9, необхідно і достатньо, щоб сума цифр його десяткового запису ділилася на 9 Доказ 1) Доведемо, що (10 n – 1) 9

10 n - 1 = 10 10 n-1 - 1 = (9 + 1) 10 n-1 - 1 = = (9 · 10 n - 1 + 10 n - 1) - 1 = = (9 · 10 n - 1 + 9 · 10 n - 2 + 10 n - 2) – 1 = = (9 · 10 n-1 + 9 · 10 n-2 +. . . + 10) – 1 = = 9 · 10 n-1 + 9 · 10 n-2+10 n-2+. . . + 9 = 9 · (10 n-1 + 10 n-2 + 10 n-2 +. . . + 1) ділиться на 9 (10 n – 1) 9

2) До десяткового запису числа х: х = аn · 10 n + аn-1 · 10 n - 1 +. . . + а 1 · 10 + а 0 додамо та віднімемо вираз (аn+ аn-1+. . . + а 0) Отримаємо: х = (аn· 10 n – аn) + (аn-1 · 10 n-1– аn- 1) +. . . + (а 1 · 10 – а 1) + (а 0 – а 0) + (аn + аn-1 +. . . + а 1 + а 0) = ділиться на 9, тому що кожне доданок містить множник ( 10 n - 1) = аn · (10 n - 1) + аn-1 · (10 n-1 - 1) +. . . + а 1 · (10 - 1) + + (аn + аn-1 +. . . + а 1 + а 0) ділиться на 9 за умовою

3) Доведемо, що якщо число х 9, то (аn+ аn-1+. . . + а 0) 9 Рівність запишемо у вигляді: х = (аn· 10 n – аn) + (аn-1 · 10 n- 1-аn-1) +. . . + (а 1 · 10 - а 1) + + (а 0 - а 0) + (аn + аn-1 +. . . + а 1 + а 0) аn + аn-1 +. . . + а 1 + а 0 = = х – (аn · (10 n – 1) + аn-1 · (10 n-1 – 1) +. . . + а 1 · (10 – 1)) У правій частині цього рівності зменшуване і віднімається кратні 9, то за теоремою подільності різниці (аn + аn-1 +. . . + а 1 + а 0) 9

Приклад Число 34578 9, тому що 3 + 4 + 5 + 7 + 8 = 27, 27 9 Число 130542 не ділиться 9, тому що 1 + 3 + 0 + 5 + 4 + 2 = 15, 15 не ділиться на 9

Теорема 16 (ознака ділимості на 3) Для того, щоб число х ділилося на 3, необхідно і достатньо, щоб сума цифр його десяткового запису ділилася на 3 Доказ аналогічний доказу ознаки ділимості на 9

Найменше загальне кратне і загальний дільник найбільший Визначення Загальним кратним натуральних чисел а і b називається число, яке кратне кожному з цих чисел Найменше з усіх загальних кратних чисел а і b називається найменшим загальним кратним цих чисел Найменше загальне кратне чисел а позначають b) та b

Загальними кратними чисел 12 і 18 є: 36, 72, 108, 144, 180 … Число 36 - найменше загальне кратне чисел 12 і 18 Пишуть: К(12, 18) = 36 Властивості К(а, b) 1. Найменше чисел а та b завжди існує і є єдиним 2. Найменше загальне кратне чисел а і b не менше більшого з даних чисел, тобто якщо а > b, то К(а, b) > а 3. Будь-яке загальне кратне чисел а і b поділяється на їх найменше загальне кратне

Визначення Загальним дільником натуральних чисел а та b називається число, яке є дільником кожного з цих чисел Найбільше з усіх загальних дільників чисел а та b називається найбільшим загальним дільником даних чисел. Найбільший загальний дільник чисел а та b позначають D(a, b) Загальними дільниками чисел 12 та 18 є числа: 1, 2, 3, 6 Число 6 – найбільший спільний дільник чисел 12 та 18 Пишуть: D(12, 18) = 6

Число 1 є спільним дільником будь-яких двох натуральних чисел а та b Визначення D(a, b) = 1, то числа а та b називаються взаємно простими Приклад Числа 14 та 15 – взаємно прості, оскільки D(14, 15) = 1

Властивості D (а, b) 1. Найбільший загальний дільник чисел а і b завжди існує і є єдиним 2. Найбільший загальний дільник чисел а і b не перевищує меншого з цих чисел, тобто якщо а

Добуток найменшого загального кратного і найбільшого загального дільника чисел а і b дорівнює добутку цих чисел, тобто К(a, b) · D(a, b) = а · b Наслідки 1) Найменше загальне кратне двох взаємно простих чисел дорівнює добутку цих чисел, тобто D(a, b) = 1 K(a, b) = a · b Наприклад, К(14, 15) = 14 15, оскільки D (14, 15) = 1

2) Ознака ділимості на складове число: Для того, щоб натуральне число а ділилося на добуток взаємно простих чисел m і n, необхідно і достатньо, щоб воно ділилося і на m, і на n Приклад 6 = 2 · 3 і D(2, 3 ) = 1, то отримуємо ознаку ділимості на 6: для того, щоб натуральне число ділилося на 6, необхідно і достатньо, щоб воно ділилося на 2 і 3 Дану ознаку можна застосовувати багаторазово

Завдання Сформулюйте ознаку ділимості на 60 Для того щоб число ділилося на 60, необхідно і достатньо, щоб воно ділилося і на 4, і на 15, де D(4, 15) = 1. У свою чергу, число буде ділитися на 15 тоді і тільки тоді, коли воно ділиться і на 3, і на 5, де D(3, 5) = 1 Таким чином ознака ділимості на 60: Для того щоб число ділилося на 60, необхідно і достатньо, щоб воно ділилося на 4, на 3 та на 5

3) Приватні, що отримуються при розподілі двох даних чисел на їх найбільший спільний дільник, є взаємно простими числами Наприклад, перевіримо, чи є число 12 найбільшим спільним дільником чисел 24 і 36. Для цього розділимо 24 і 36 на 12. Отримаємо відповідно числа 2 і 3 де D (2, 3) = 1, тобто 2 і 3 є взаємно простими. Отже, D(24, 36) = 12

Прості та складові числа Визначення Простими називаються числа, які діляться тільки на себе і на одиницю Визначення Складовими називаються числа, які мають більше двох дільників . – прості, числа 4, 25, 102 і т. д. – складові

Властивості простих чисел 1. Якщо просте число p ділиться на деяке натуральне число n, де n ≠ 1, воно збігається з n Дійсно, якщо p ≠ n, то р має три дільники: 1, n і p, а тоді воно не просте 2. Якщо p і q – прості числа і р ≠ q, то p не ділиться на q Якщо p – просте число, воно має тільки два дільники: 1 і р. За умовою q теж просте, отже q ≠ 1 і q ≠ р Отже, q не є дільником числа p Числа 17 та 11 – прості, отже 17 не ділиться на 11

3. Якщо натуральне число a не ділиться на просте число p, то а і p взаємно прості, тобто D(а, р) = 1 Наприклад, 25 не ділиться на 7, отже 25 та 7 – взаємно прості 4. Якщо добуток двох натуральних чисел а і b ділиться на просте число p, то хоча б одне з них ділиться на p Наприклад, 25 39 = 975. Число 975 ділиться на 3, тому що 9 + 7 + 5 = 21. Але число 25 не ділиться на 3, отже, 39 ділиться на 3

5. Якщо натуральне число більше 1, воно має хоча б один простий дільник Справді, всі прості числа мають прості дільники – самі ці числа, складові числа можна розкладати на множники до тих пір, поки вони не стануть простими числами Наприклад, 240 > 1 , значить має хоча б один простий дільник, це число 2 (або 5)

6. Найменший простий дільник складового числа а не перевищує Доказ Нехай а – складове число, а р – його найменший простий дільник. Тоді а = Рb. При цьому р b, т. К. Інакше простий дільник числа b був би менше, ніж р, а тоді а мало б прості дільники, менші ніж р. Помножимо обидві частини нерівності на нар. Отримаємо р2 рb рb = а. Тому, р2 а, тобто

Теорема – Основна теорема арифметики Будь-яке складове число можна єдиним чином представити у вигляді добутку простих множників де а 1, а 2, а 3, …, аk – прості числа, n 1, n 2, n 3, … , nk – показники, с якими входять прості числа у розкладання числа х Таке розкладання числа на прості множники називають канонічним

Приклад 110 = 2 · 5 · 11 - добуток простих множників є розкладання числа 110 на прості множники Два розкладання числа на прості множники вважають однаковими, якщо вони відрізняються один від одного лише порядком множників 110 = 2 · 5 · 11 = 5 · 11 · 2 - одне й те саме розкладання

Спосіб розкладання числа на прості множники 90 2 45 3 15 3 5 5 тільки прості числа 1 Таким чином, 90 = 2 · 3 · 5 · 1 = 2 · 32 · 5 60 = 22 · 3 · 5; 72 = 23 · 32

Решето Ератосфена Ератосфеном (III ст. до н. е.) був придуманий спосіб отримання простих чисел, що не перевищують натурального числа а (решета Ератосфена) Знайдемо всі прості числа до 50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Нескінченність безлічі простих чисел Теорема, доведена Евклідом Безліч простих чисел нескінченно Доказ Нехай безліч простих чисел звичайно і складається з чисел: 2, 3, 5, 7, . . . , p, де р - найбільше просте число. Знайдемо добуток усіх простих чисел 2 3 5 7 . . . p = а. Додамо до одиницю. Число а + 1 простим не є, тому що а + 1 > р найбільшого простого числа (за припущенням)

Нехай а + 1 - складове число (а + 1) повинно мати хоча б один простий дільник q р. Так як число а = 2 · 3 · 5 · р також ділиться на це просте число q, то і різниця (а + 1) - а ділиться на q, тобто число 1, ділиться на q, що неможливо Отже, число а не є ні простим, ні складовим. Але цього теж не може бути - будь-яке число, відмінне від 1, або просте, або складове. Отже, пропозиція про те, що безліч простих чисел кінцеве і є найбільше просте число, невірно, і значить, безліч простих чисел нескінченне

Способи знаходження найбільшого загального дільника та найменшого загального кратного чисел 1 спосіб Щоб знайти НОД двох чисел, можна перерахувати всі їхні спільні дільники та вибрати з них найбільший , 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 Дільники числа 486: 1, 2, 3, 6, 9, 27, 54, 81, 162, 243, 486 2, 3, 6 Найбільшим спільним дільником є число 6

Щоб знайти НОК двох чисел, можна перерахувати деякі їх загальні кратні і вибрати з них найменший Приклад Дані числа 60 і 48 Кратні числа 60: 60, 120, 180, 240, 300, 360, 420, 480, 540, . . . Кратні числа 48: 48, 96, 144, 192, 240, 288, 336, 384, 432, 480, . . . Загальні кратні числа 60 і 48: 240, 480, . . . Найменшим загальним кратним є число 240

2 спосіб - заснований на розкладанні даних чисел на прості множники Алгоритм знаходження найбільшого загального дільника даних чисел: 1) уявити кожне дане число в канонічному вигляді; 2) утворити добуток загальних всім даних чисел простих множників, кожен із найменшим показником, з яким він входить у всі розкладання даних чисел; 3) знайти значення цього твору – він і буде найбільшим спільним дільником даних чисел

Приклад Дано два числа 3600 і 288 Канонічне розкладання цих чисел: 3600 = 24 32 52; D(3600, 288) = 24 32 = 144 288 = 25 32

Алгоритм знаходження найменшого загального кратного даних чисел: 1) уявити кожне дане число в канонічному вигляді; 2) утворити добуток всіх простих множників, що у розкладах даних чисел, кожен із максимальним показником, з яким він входить у всі розкладання даних чисел; 3) знайти значення цього твору - воно і буде найменшим загальним кратним даних чисел

Приклад Дано два числа 3600 і 288 Канонічне розкладання цих чисел: 3600 = 24 32 52; 288 = 25 32 K (3600, 288) = 25 32 52 = 7200

3 спосіб - алгоритм Евкліда Алгоритм Евкліда заснований на наступних твердженнях: 1. Якщо а поділяється на b, то D(a, b) = b 2. Якщо a = bq + r і r

Src="https://present5.com/presentation/3/71306524_41475257.pdf-img/71306524_41475257.pdf-55.jpg" alt="Нехай а > b Якщо а ділиться на b, то D(a , b) = b"> Пусть а > b Если а делится на b, то D(a, b) = b Если при делении а на b, получается остаток r, то а = bq + r и D(a, b) = D(b, r) Найдем D(b, r) Если b делится на r, то D(b, r) = r и тогда D(a, b) = r Если при делении b на r получается остаток r 1, то b = rq 1 + r 1, и тогда D(r, r 1) = D(b, r) = D(a, b) Найдем D(r, r 1)!}

Продовжуючи описаний процес, отримуємо менші і менші залишки. В результаті отримаємо залишок, на який ділитиметься попередній залишок. Цей найменший, відмінний від нуля, залишок і буде найбільшим загальним дільником чисел а і b Знайти НОК і НОД чисел можна за формулою: К(a, b) · D(a, b) = а · b К(а, b) = а · b: D(a, b) = а · b: К(а, b)

Приклад Знайдіть за алгоритмом Евкліда найбільший спільний дільник чисел 2585 і 7975 = 2585 3 + 220 2585 = 220 11 + 165 220 = 165 1 + 55 165 = 55 3 + 0 Значить, D(79 2585) = = (7975 2585): 55 = = 20615375: 55 = 374825

7975 7555 2585 220 385 220 165 165 0 55 3 165 1 220 11 2585 3

Кажуть, що ціле число a ділиться на ціле число b, відмінне від 0, якщо таке ціле число з певне однозначно, що a = b * c.

евклід лема арифметика позиційний

1) Ставлення ділимості рефлексивно, тобто. . Дійсно, число 1 а=а*1
2) Ставлення подільності транзитивно, тобто. якщо

З цього випливає, що a = (c * k) * t = c * (k * t) = c * m

А це означає, що ас

3) Якщо аb, то (-a)b, (-a)(-b), a(-b)
4) Якщо ac та bc, то (ab)c

a = c * t, b = c * k (ab) = c * tc * k = c * (tk) (ab) c

АЛЕ: зворотне твердження неправильне.

5) Якщо ab та cZ (довільне число), то (a*c)b
6) Якщо кожне з чисел a1, a2…an ділиться на b, то (r1a1+…+rnan)b, де r1,…,rnZ
7) Якщо ac, b неc, то (a+b)нес

Нехай (a + b) = t і tc, t-a = b це суперечить умові.

8) 0на будь-яке число, 0
9) Будь-яке ціле число1, т.к. всяке число можна записати як а=1*а
10) На 0 ділити не можна: а=0*с, якщо а0, це рівність неправильно; якщо а=0, маємо 0=0*с, сZ - у разі порушується умова єдиності визначення с.
11) Якщо ab, то. a = b * c, де b, cZ

Теорема про поділ із залишком

Розділити ціле число а на ціле число b0, це знайти такі цілі числа q і r, що a = bq + r, 0

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

Доведення:

1) Існування:

Розглянемо цілі числа кратні b. Це числа -2b,-b,b,2b... і нехай bq-останнє кратне b, що не перевищує число а, тоді воно є найбільшим серед записаних кратних. І тут b(q+1)>a. Отримали:

bqa

Нехай a-bq = r. Тоді отримаємо: a = bq + r, причому 0r<

Цей доказ проходить для випадку b>0.

Тепер нехай b<0,тогда (-b)>0.

Тоді a = (-b) * q + r, a = b * (-q) + r, де 0r<-b, -b=, где b<0, 0r<

Таким чином, розподіл із залишком можливий за будь-яких а і b0

2) Єдиність:

Припустимо, що це не так:

a=bq1+r1 та a=bq2+r2;

b(q1-q2) = r2-r1; де 0r1,r2<;

Де 0r2-r1<, r2>r1.

Рівність можлива, якщо, => q1 = q2, r1 = r2.