Page 39 - 4570

38

Доведення. Якщо множина А не збігається з N. то існують натуральні
числа, які не мають властивості Р. Згідно з принципом найменшого числа серед
таких чисел є найменше. Позначимо його m. Із умови а) випливає, що m  1,
тому число k = m - 1 – натуральне. Оскільки k < m i m – найменше серед чисел,
що не мають властивості Р. то k цю властивість має. Але тоді із умови б)
випливає, що число m = k + 1 також має властивість Р. Отже, припущення А 
N приводить до суперечності.
Якщо позначити через P(n) той факт, що натуральне число n має
властивість Р. то принцип математичної індукції можна переформулювати
дуже коротко: якщо Р(1) і для, будь-якого натурального n із припущення, Р(n)
випливає P(n + 1), то {n  N | P(n)} = N.
Принцип математичної індукції інколи називають «Принципом доміно».
Якщо кісточки доміно виставити в ряд так, щоб кожна кісточка при падінні
збивала сусідню, а потім штовхнути першу, то впадуть усі кісточки.
Існують різні модифікації принципу математичної індукції. Так, нас може
цікавити наявність властивості Р лише в чисел певного вигляду (наприклад, в
усіх n  2000 або в усіх парних чисел). У багатьох випадках зручним є варіант,
коли в б) припускається, що властивість Р має не тільки число n, а й усі числа,
менші за n.

2. Теорема про ділення з остачею

Відносно операцій додавання і множення множина N є замкненою. Але
обернена до додавання операція віднімання для натуральних чисел виконлива
не завжди. Тому часто буває зручно замість множини N розглядати більшу
множину Z цілих чисел, яка є замкненою також і відносно віднімання. Стосовно
ділення множина Z залишається незамкненою.
Теорема 1.12 (про ділення з остачею). Для кожної пари цілих чисел, a і b,
b  0, можна знайти такі цілі числа q і r, що
a = qb + r і 0  r < |b| (1.3)
Числи q і r цими умовами визначаються однозначно.
Доведення. Спочатку доведемо існування чисел q і r. Якщо а = 0, то
можна взяти q = r = 0. Тому далі вважатимемо, що а  0. Найперше розглянемо
випадок, коли а > 0 і b > 0. Позначимо через А множину А = {a - nb | n  Z}.
Серед її елементів є додатні числа (таким буде, наприклад, число а - (-1)b = а +
b). Тому, згідно з принципом найменшого числа, серед невід’ємних чисел із
множини А є найменше. Позначимо його через r і нехай r = а - qb – зображення
r як елемента множини А. Легко бачити, що r < b, бо в противному разі
множина А містила б невід’ємне число r - b = а - (q + 1)b, яке менше від r.
Оскільки r > 0 і а = qb + r, то числа q і r шукані.
Для доведення однозначності чисел q і r припустимо, що пара (q 1; r 1) також
задовольняє умовам а = q 1b + r 1 і 0  r1 < |b|. Тоді із q 1b + r 1 = qb + r випливає
|q 1 - q||b| = |r - r 1|. Очевидно, що |r - r 1| < |b|, бо числа r і r 1 лежать в інтервалі [0,
|b|). Звідси |q 1 - q||b| < |b| і |q 1 - 1| < 1. Оскільки число q 1 - q ціле, то |q 1 - q| = 0 і q 1
= q. Але тоді r 1 = (q – q 1)b + r = r, що й треба було довести.