Кажуть, що ціле число а кратне цілому числу b (а ділиться на ціле число b без лишку), якщо існує таке ціле число q, що а = bq. Запис а ⋮ b означає, що а кратне на b. Довести такі твердження:
а) а ⋮ b ∧ b ⋮ c ⇒ а ⋮ c;
б) а ⋮ b ∧ b ⋮ c ⇒ (а + b) ⋮ c;
в) а ⋮ c ∧ t ∈ Z ⇒ аt ⋮ c;
г) а ⋮ c ∧ b ⋮ c ∧ t₁ ∈ Z ∧ t₂ ∈ Z ⇒ (аt₁ + bt₂) ⋮ c;
д) а ⋮ b ⇒ а ⋮ (− b);
е) а ⋮ b ∧ b ⋮ a ⇔ |а| = |b|,
де Z — множина цілих чисел.

Ціле число r називають лишком від ділення цілого числа a на ціле число b, якщо існує таке ціле число q, що а = bq + r, причому 0 ≤ | b|. Довести такі твердження:
а) якщо а₁ = bq₁ + r₁ і а₂ = bq₂ + r₂, то лишки від ділення на b чисел а₁ + а₂ і r₁ + r₂ однакові;
б) якщо а₁ = bq₁ + r₁ і а₂ = bq₂ + r₂, то лишки від ділення на b чисел а₁а₂ і r₁r₂ однакові;
в) якщо а₁ = bq₁ + r₁ і а₂ = bq₂ + r₂, то лишки від ділення на b чисел а₁ − а₂ і r₁ − r₂ однакові.

Числа а і b дають однакові лишки при діленні на c тоді і тільки тоді, коли (а − b) ⋮ c. Довести це.

Використавши задачу 2, знайти лишок від ділення на 7 таких чисел:
1) 2¹³⁵; 2) 1979¹⁹⁸⁰; 3) 143³³ − 16 · 24²⁰; 4) 1З¹⁴ − 18¹³.

Знайти лишок від ділення на 5 таких чисел:
1) 2¹⁴⁹; 2) 1979¹⁹⁷⁹; 3) 74²⁵ − 9 · 36⁸⁴; 4) 1З¹⁴ − 19¹⁹.

Натуральне число d називають найбільшим спільним дільником чисел а і b, якщо:
1) а ⋮ d ∧ b ⋮ d;
2) (а ⋮ t ∧ b ⋮ t) ⇒ d ⋮ t.
Нехай а і b — цілі числа, що не дорівнюють нулю. Розглянемо таку множину:

Довести, що:
а) а ∈ M, b ∈ M;
б) у множині M є додатні числа.

Позначимо через d найменше додатне число, яке є у множині M. Довести, що:
в) всі числа множини M кратні d;
г) число d є найбільшим спільним дільником чисел a і b.

Рівняння ах + by = с з цілими коефіцієнтами a, b, c і двома невідомими x, y має цілі розв’язки тоді і лише тоді, коли число с ділиться на найбільший спільний дільник чисел a і b. Довести це.

Цілі числа a і b називають взаємно-простими, якщо їхній найбільший спільний дільник дорівнює 1. Довести, що числа a і b взаємно-прості тоді й лише тоді, коли існують такі цілі числа s, t ∈ Z, що as + bt = 1.

Якщо число a взаємно-просте з кожним із чисел b і c, то воно взаємно-просте також з їхнім добутком bc. Довести це, використавши задачу 8.

Якщо аb ⋮ c і число b взаємно-просте з c, то а ⋮ c. Довести це.

Якщо а ⋮ b і а ⋮ c, причому b і c взаємно-прості, то а ⋮ bc. Довести це, використавши попередню задачу.

Натуральне число а > 1 називають простим, якщо воно не ділиться ні на які натуральні числа, крім самого себе і на 1. Довести, що будь-які два різних простих числа взаємно-прості.

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

Довести, що кожне натуральне число розкладається на прості множники однозначно. Це означає, що коли а = p₁ p₂ ⋯ p_s і а = q₁ q₂ ⋯ q_t — два розклади числа а на прості множники, то s = t і кожне просте число серед чисел {p_j} і чисел {q_k} зустрічається однакову кількість разів.

Зауваження. Змістом задач 13—14 є твердження, що називається головною теоремою арифметики.

Розклад кожного натурального числа а > 1 на прості множники завжди можна подати так: $$a = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}\qquad (k_j > 0,\quad j=1, 2,~ ..., m),$$ де \(p_j\) — прості числа, причому \(p_1 < p_2 < \cdots < p_m^{k_m}\). Такий розклад називають канонічним. Із задачі 14 випливає, що він однозначний. Знайти канонічні розклади на прості множники таких чисел:
а) 5096; б) 5445; в) 1312; г) 3279; д) З0 030; е) 4961.

Нехай \(a = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}\) — канонічний розклад натурального числа а на прості множники. Дати опис натуральних дільників числа а. Скільки таких дільників має це число?

Довести, що для будь-якого n ∈ Z число n⁵ — 5n³ + 4n ділиться на 120.

Довести, що для будь-якого невід’ємного цілого п число 11^{n + 2} + 12^{2n + 1} ділиться на 133.

Довести, що для будь-якого n ∈ Z число \[ {n^3\over 6} - {n^2\over 2} + {n\over 3}\] ціле.

Якщо n — непарне число, то n² — 1 ділиться на 8. Довести це.

Якщо n і m — непарні числа, то (n² — m²) ⋮ 8. Довести це.

Якщо n не ділиться на 3, то (n² — 1) ⋮ 3. Довести це.

Якщо p і q — прості числа, більші від 3, то (p² — q²) ⋮ 24. Довести це.

Довести, що лишок від ділення на 6 чисел n і n³ однаковий.

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

Число p — просте. Скільки є цілих додатних чисел, які менші від pⁿ і взаємно-прості з ним (n — натуральне число).

Якщо p — просте число, більше від 3, то принаймні одне з чисел p + 10 або p + 14 не просте. Довести це.

Які натуральні числа можна, а які не можна подати у вигляді добутку двох цілих додатних множників, менших за саме число?

Довести, що добуток n перших натуральних чисел (n > 1) ділиться на суму цих чисел тоді й лише тоді, коли число n + 1 не просте.

Які натуральні числа мають непарну кількість натуральних дільників?

Довести, що для будь-якого натурального n число 2ⁿ + 1 не ділиться на 7.

Довести, що для будь-якого натурального n число 9ⁿ + 1 не може закінчуватись двома чи більше нулями.

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

Довести, що натуральне число й сума його цифр дають однаковий лишок при діленні на 9.

Нехай \( a = \overline{\alpha_n\alpha_{n-1} ... \alpha_1\alpha_0}\) — натуральне число ({\(\alpha_j\)} — його цифри). Довести, що числа \(a\) і \( b = \overline{\alpha_1\alpha_0}\) мають однаковий лишок при діленні на 4.

Нехай \( a = \overline{\alpha_n\alpha_{n-1} ... \alpha_1\alpha_0}\) — натуральне число. Довести, що числа \(a\) та \[ c = \alpha_0 - \alpha_1 + \alpha_2 - \alpha_3 \cdots (-1)^n \alpha_n\] мають однаковий лишок при діленні на 11.

Методом від супротивного довести, що простих чисел безліч.

Довести, що будь-яке просте число p > 2 можна подати як різницю квадратів двох натуральних чисел.

Якщо натуральне число n не є степенем двійки, то число 2ⁿ + 1 не просте. Довести це.

Лишок від ділення будь-якого простого числа на З0 дорівнює 1 або є простим числом. Довести це.

Якщо а = bq + с, де a, b, с, q — цілі числа, то найбільший спільний дільник чисел а і b і найбільший спільний дільник чисел b і с однакові. Довести це.

Чому дорівнює найбільший спільний дільник натурального числа а і нуля?

Нехай а і b — натуральні числа, r₁ — лишок від ділення a на b, r₂ — лишок від ділення b на r₁ (якщо r₁ ≠ 0), r₃ — лишок від ділення r₁ на r₂ (якщо r₂ ≠ 0), і т. д. доти, поки в лишку не отримаємо 0. Pаніше чи пізніше це трапиться, бо b > r₁ > r₂ > r₁ ... . Припустимо, що r_n ≠ 0, а r_{n + 1} = 0. Довести, що r_n — найбільший спільний дільник чисел а і b.

Зауваження. Описане в задачі відшукання найбільшого спільного дільника двох чисел було відоме ще математикам стародавньої Греції. Тепер цей метод називають алгоритмом Евкліда.

Застосувавши алгоритм Евкліда (див. попередню задачу), знайти найбільший спільний дільник таких пар чисел: 1) 2173 і 2747; 2) 6499 і 2077; 3) 12769 і 7571; 4) 3503 і 2231.

Якщо найбільший спільний дільник чисел а і b дорівнює d, a = a₁d, b = b₁d, то числа a₁ і b₁ взаємно-прості. Довести це.

Натуральне число називають найменшим спільним кратним цілих чисел а і b, відмінних від нуля, якщо:
а) g ⋮ a ∧ g ⋮ b;
б) (f ⋮ a ∧ f ⋮ b) ⇒ f ⋮ g.
Нехай d — найбільший спільний дільник чисел а і b, a = a₁d, b = b₁d. Довести, що g = a₁b₁d — найменше спільне кратне чисел а і b.

Ціле число а тоді й лише тоді ділиться на кожне з чисел b і c, коли воно ділиться на їх найменше спільне кратне. Довести це.

Скільки цілих додатних чисел, які не перевищують 10 000, ділиться одночасно на 42 і 66?

Використавши розв'язання задач 43 й 46, знайти найменше спільне кратне таких пар чисел: 1) 3977 і 1271; 2) 2987 і 1957; 3) 527 і 1189; 4) 10 403 і 114 433.

Якщо (а − b) ⋮ c, то найбільший спільний дільник чисел a і c дорівнює найбільшому спільному дільникові чисел b і c. Довести це.

Якщо натуральне число ділиться на 99, то сума його цифр не менша від 18. Довести це.

Довести, що ні при якому цілому n число n² + Зn + 5 не ділиться на 121.

Сума кількох послідовних натуральних чисел дорівнює 1000. Які це числа? Знайти всі розв’язки.

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

Якщо a = 2^{k − 1} · (2^k − 1), причому 2^k − 1 — просте число, то сума всіх натуральних дільників числа a дорівнює 2a. Довести це.

Якщо a і b — непарні цілі числа, то a³ − b³ ділиться на 4 тоді й лише тоді, коли (a − b) ⋮ 4.

Довести, що для будь-якого натурального n число 5ⁿ + 2 · З^{n − 1} + 1 ділиться на 8.

Довести, що для будь-якого натурального n число 2^{5n − 1} + 2^{5n − 2} + + 2² + 2 + 1 ділиться на 31.