Подільність: відповіді до задач

Відповіді до задач з теорії подільності

Вишенський В.А., Перестюк М.О., Самоленко А.М.
Збірник задач з математики. — Київ, Вища школа, 1982, 334 с. §1.

1.
a) a = bq₁ ∧ b = cq₂ ⇒ a = c(q₁ q₂) ⇒ a ⋮ c.
б) a = bq₁ ∧ b = cq₂ ⇒ a + b = c(q₁ + q₂) ⇒ (a + b) ⋮ c.
в) a = cq ⇒ at = c(qt) ⇒ at ⋮ c.
г) Випливає з б) і в).
д) a = bq ⇒ a = ( − b) ( − q) ⇒ a ⋮ ( − b).
e) a = bq₁ ∧ b = cq₂ ⇒ a = a q₁q₂ ⇒ q₁q₂ = 1 ⇒ q₁ = 1 ∨ q₁ = − 1, тому a = b або a = − b.

2.
а) Нехай r₁ + r₂ = bq + r, 0 < ≤ r < | b |. Тоді a₁ + a₂ = b (q₁ + q₂) + r₁ + r₂ = b (q₁ + q₂ + q) + r.
б) Нехай r₁r₂ = bq + r, 0 ≤ r < | b |. Тоді a₁a₂ = (bq₁ + r₁)(bq₂ + r₂) = b²q₁q₂ + bq₁r₂ + br₁q₂ + r₁r₂ = b(bq₁q₂ + q₁r₂ + r₁q₂ + q) + r.
в) Нехай r₁ − r₂ = bq + r, 0 ≤ r < | b |. Тоді a₁ − a₂ = = b (q₁ − q₂) + r₁ − r₂ = b (q₁ − q₂ + q) + r.

3. Наслідок твердження 2в.
4.
1) 2¹³⁵ = (2³)⁴⁵ \(\stackrel{7}{\equiv}\) 1⁴⁵ = 1.
2) 1979¹⁹⁸⁰ = (7·282 + 5)¹⁹⁸⁰ \(\stackrel{7}{\equiv}\) 5¹⁹⁸⁰ = 5^{6 · 330} = (5⁶)³³⁰ \(\stackrel{7}{\equiv}\) 1,
2) бо 5² \(\stackrel{7}{\equiv}\) 4; 5³ \(\stackrel{7}{\equiv}\) 4 · 5 \(\stackrel{7}{\equiv}\) 6; 5⁶ \(\stackrel{7}{\equiv}\) 6 · 6 \(\stackrel{7}{\equiv}\) 1.
3) 143³³ − 16 · 24²⁰ = (7·20 + 3)³³ − (7·2 + 2) · (7·3 + 3)²⁰ \(\stackrel{7}{\equiv}\) 3³³ − 2 · 3²⁰ = 3^{6 · 5 + 3} − 2 · 3^{6 · 3 + 2} \(\stackrel{7}{\equiv}\) 3³ − 2 · 3² \(\stackrel{7}{\equiv}\) 6 − 2 · 2 = 2,
3) бо 3² \(\stackrel{7}{\equiv}\) 2; 3³ \(\stackrel{7}{\equiv}\) 2 · 3 = 6; 3⁶ \(\stackrel{7}{\equiv}\) 6 · 6 \(\stackrel{7}{\equiv}\) 1.

Примітка (Олександр Рудик). В описі розв'язання задач використано такий порядок дій.

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

Задачу 5, для якої подано лише відповіді, потрібно розв'язувати саме таким чином. У задачах з дво- і більше кратним піднесенням до степеня, досліджувати періодичність лишків потрібно буде відповідно двічі й більше разів.

У 2003 році на ІІІ етапі Всеукраїнської учнівської олімпіади з інформатики було запропоновано саме таку задачу.

5. Остача, 34 бали
Для зручності запису умови позначимо a^b через a ^ b.

Завдання
Створіть програму remain.*, яка обчислить остачу від ділення на a₀ числа

a₁^ (a₂^ (a₃^…(a_{n – 2}^ (a_{n – 1}^ a_n))…)).

Вхідні дані
Файл remain.dat містить у вказаному порядку натуральні числа n, a₀, a₁, a₂, …, a_n у межах від 1 до 2¹⁶, n < 9.

Вихідні дані
Файл remain.res має міститти лише шукану остачу.

Приклад

remain.dat	remain.res
`5 4 3 5 7 9 11`	`3`

5. 1) 2. 2) 4. 3) 0. 4) 0.

6.
а) Взявши х = 1, у = 0, дістанемо: ах + by = а. Отже, а ∈ М. Аналогічно b ∈ М.
б) Числа а, − а, b, − b належать до М. Принаймні одне з них додатне.
в) Нехай d = ах₀ + by₀. Візьмемо будь-яке число с = ах + by ∈ М і поділимо його на d з лишком: с = dq + r, 0 ≤ r < d. Звідси

r = с − dq = а(х − x₀q) + b(у − y₀q) ∈ М.

d — найменше додатне число, яке є в множині M, тому r = 0, тобто с ⋮ d.
г) Із а) і в) випливає, що a ⋮ d і b ⋮ d. Отже, d — спільний дільник чисел a і b. Якщо a ⋮ t і b ⋮ t, то d = ах₀ + by₀ ⋮ t (див. задачу 1г). Отже, d — найбільший спільний дільник чисел а і b.

7. Безпосередній наслідок попередньої задачі.
8. Безпосередній наслідок задачі 6.
9. Якщо a взаємно-просте з b і c, то існують такі цілі числа p₁, p₂, q₁, q₂, що

ap₁ + bp₂ = 1, aq₁ + cq₂ = 1.

Перемноживши почленно ці дві рівності, дістанемо

a(ap₁q₁ + cp₁q₂ + bp₂q₁) + bc(p₂q₂) = 1.

Згідно з задачею 8, ця рівність показує, що числа a та bc взаємно-прості.

10. Якщо число b взаємно-просте з c, то існують числа t₁ і t₂, що bt₁ + ct₂ = 1 (див. задачу 8). Помножимо цю рівність на a:

abt₁ + cat₂ = a.

ab ⋮ c, і c ⋮ c, тому ліва частина останньої рівності кратна c, а тому a ⋮ c.

11. a ⋮ b ⇒ a = bq, q ∈ Z. bq ⋮ c і b взаємно-просте з c, то q ⋮ c, тобто q = ct, t ∈ Z. Отже, a = bct, а це означає, що a ⋮ cb.

12. Припустимо, що числа a і b прості, але не взаємно-прості. Нехай d > 1 — їхній найбільший спільний дільник. Тоді a ⋮ d і b ⋮ d, а тому a = d і b = d, звідки a = b.

13. Нехай p₁ > 1 — найменше число, на яке ділиться а: a = p₁a₁. Число p₁ просте, бо інакше його дільник, відмінний від 1 і p₁, був би дільником числа а, меншим від p₁. Якщо a₁ = 1, то a = p₁, тобто само воно є простим числом. Якщо a₁ > 1,то з ним повторюємо спочатку всі міркування. На другому кроці дістанемо

a = p₁p₂a₂,

де p₁ і p₂. Маємо: a > a₁ > a₂ > ..., тому через певну кількість кроків прийдемо до рівності

a = p₁p₂ ⋯ p_sa_s,

де a_s = 1, а p₁, p₂, ..., p_s — прості числа.

14. Коли б серед чисел q_j не було числа p₁, то всі q_j були-б взаємно-прості з p₁ (див. задачу 12). Але тоді також число a = q₁q₂ ⋯ q_t було б взаємно-просте з p₁ (див. задачу 9). Проте це не так, бо a ⋮ p₁ і p₁ > 1. Отже, серед чисел q₁, q₂, ..., q_t є число p₁. Нехай це буде q₁. Скоротивши рівність p₁p₂ ⋯ p_s = q₁q₂ ⋯ q_t на p₁, дістанемо рівність p₂p₃ ⋯ p_s = q₂q₃ ⋯ q_t. Повторивши попередні міркування для цих двох добутків простих чисел, дійдемо висновку, що серед чисел q₂, q₃. ..., q_t є число p₂ і т. д. Через s чи t таких кроків вичерпаються або всі прості числа p_j або всі q_j. Але тоді неодмінно вичерпаються і прості числа з іншого боку рівності, бо добуток простих чисел не може дорівнювати 1. Отже, s = t і теорему доведено.

15. а) 2³ · 7² · 13; б) З² · 5 · 11²; в) 2⁵ · 41; г) 11 · 17²; д) 2 · 3 · 5 · 7 · 11 · 13; е) 11² · 41.

16. Із основної теореми арифметики (задача 14) випливає, що додатним дільником числа а може бути тільки число виду \[b = p_1^{t_1} p_2^{t_2} \cdots p_m^{t_m},\] де 0 ≤ t₁ ≤ k₁, 0 ≤ t₂ ≤ k₂, ..., 0 ≤ t_m ≤ k_m. Звідси ж випливає, що числа b не можуть бути однакові, якщо набори значень t_j в них різні. Нарешті, кожне число b вказаного виду є дільником числа а. Справді, \[a = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m} = p_1^{t_1} p_2^{t_2} \cdots p_m^{t_m} p_1^{k_1-t_1} p_2^{k_2-t_2} \cdots p_m^{k_m-t_m} = bc,\] причому c — ціле число, бо 0 ≤ k₁ − t₁, 0 ≤ k₂ − t₂, ..., 0 ≤ k_m − t_m. Отже, число а має (k₁ + 1)(k₂ + 1)⋯(k_m + 1) дільників (для показника t_j є (k_j + 1) можливостей, причому для різних j ці можливості можна реалізувати незалежно).

17. 120 = 2³ · 3 · 5. Число а ділиться на 120 тоді й лише тоді, коли воно ділиться на 2³, на 3 і на 5. Дане число

a = n⁵ − 5n³ + 4n = (n − 2)(n − 1)n(n + 1)(n + 2),

ділиться на всі ці числа, бо при будь-якому n ∈ Z воно є добутком п’яти послідовних цілих чисел. Серед таких чисел одне ділиться на 5, принаймні одне — на 3, принаймні одне — на 4 і, крім того, ще хоча б одне — на 2.

18. Можна застосувати метод математичної індукції. При n = 0 маємо: a₀ = 11² + 12 = 133, що кратне 133. Припустимо, що число \[a_n = 11^{n+2} + 12^{2n+1}\] ділиться на 133. Тоді. \[a_{n+1} = 11^{n+3} + 12^{2n+3} = 11\cdot 11^{n+2} + 144\cdot 12^{2n+1} \stackrel{133}{\equiv} 11\cdot 11^{n+2} + 11\cdot 12^{2n+1} = 11a_n.\] Отже, a_{n + 1} ⋮ 133, якщо a_n ⋮ 133. Згідно з принципом математичної індукції всі числа a₀, a₁, a₂, ..., діляться на 133.

19. \[{n^3\over 6} - {n^2\over 2} + {n\over 3} = {(n-2)(n-1)n\over 6}.\] 20. Якщо n = 2k + 1, то n² − 1 = 4k(k + 1). Одне з чисел k або k + 1 парне.

21. Можна використати попередню задачу: n² − m² = (n² − 1) − (m² − 1).

22. Якщо \(n\stackrel{3}{\equiv} 1\) або \(n\stackrel{3}{\equiv} 2\), то \(n^2\stackrel{3}{\equiv} 1\) (див. задачу 2).

23. p² − q² = (p² − 1) − (q² − 1). Далі використати задачі 21, 22.

24. n³ − n = (n − 1) n (n + 1) ⋮ 6. Далі див. задачу 3.

25. Наслідок задач 24 і 3.

26. pⁿ − p^{n − 1}.

27. Одне з двох даних чисел ділитиметься на 3.

28. Можна всі, крім 1, простих чисел і квадратів простих чисел.

29. \[{1\cdot 2\cdot 3\cdot~\cdots~\cdot n\over 1+2+3+\cdots +n} = {2(n-1)!\over n+1} = a.\] Потрібно з’ясувати, за яких умов число а ціле. Якщо число n + 1 парне, то серед чисел 1, 2, ... , n − 1 є (n + 1)/2, а тому число a ціле. Нехай число n + 1 непарне, але не просте. Якщо воно не є квадратом простого числа, то його можна подати як добуток двох менших різних між собою чисел. Обоє вони є множниками числа (n − 1 )!, а тому число а й у цьому випадку є ціле. Якщо а є квадратом простого числа p, то серед множників числа (n − 1)! є p і 2p. Отже, число а й у цьому випадку буде ціле. Таким чином, число а не ціле лише тоді, коли n + 1 просте число.

З0. Квадрати натуральних чисел (див. задачу 16).

31. \(2^{3k}\stackrel{7}{\equiv} 1\), \(2^{3k+1}\stackrel{7}{\equiv} 2\), \(2^{3k+2}\stackrel{7}{\equiv} 4\). Отже, лишок від ділення на 7 числа 2ⁿ + 1 дорівнює 2, 3 або 5.

32. \(9^{n}+1\stackrel{4}{\equiv} 2\), а число, що закінчується двома чи більше нулями, ділиться на 4.

33. Нехай a = 10^kα_k + 10^{k − 1}α_{k − 1} + ⋯ + 10α₁ + α₀, де α_k, α_{k − 1}, ..., α₁, α₀ — цифри числа. Тоді

a − (α_k + α_{k − 1} + ⋯ + α₁ + α₀) = (10^k − 1) α_k + (10^{k − 1} − 1) α_{k − 1} + ⋯ + (10 − 1) α₁

ділиться на 9, а отже, й на 3, бо 10^s − 1 = (10 − 1) (10^{s − 1} + 10^{s − 2} + ⋯ + 10 + 1). Далі див. задачу 3. Можна міркувати і так. \(10 \stackrel{3}{\equiv} 1\), то \(10^s \stackrel{3}{\equiv} 1\), якщо s — натуральне число. Тому

a = 10^kα_k + 10^{k − 1}α_{k − 1} + ⋯ + 10α₁ + α₀ \(\stackrel{3}{\equiv}\) α_k + α_{k − 1} + ⋯ + α₁ + α₀

(див. задачу 2). Доведене твердження обгрунтовує відому ознаку подільності на 3.

34. Див. розв’язок попередньої задачі.

35. a − b ділиться на 100, а отже, й на 4.

36. a − c = (10 + 1) α₁ + (10² − 1) α₂ + (10³ + 1) α₃ + (10⁴ − 1) α₄ + ⋯ + (10ⁿ − (− 1)ⁿ) ⋮ 11, бо 10^{2k + 1} + 1 ⋮ 11 і 10^2k − 1 ⋮ 11. Справді, \(10^2 \stackrel{11}{\equiv} 1\), а тому \(10^{2k+1} + 1 \stackrel{11}{\equiv} 10 + 1 \stackrel{11}{\equiv} 0\) і \(10^{2k} - 1 \stackrel{11}{\equiv} 1 - 1 \stackrel{11}{\equiv} 0\). Із доведеного твердження випливає така ознака подільності на 11. Число \( a = \overline{\alpha_n\alpha_{n-1} ... \alpha_1\alpha_0}\) ділиться на 11 тоді й лише тоді, коли число \[\alpha_0 - \alpha_1 + \alpha_2 - \alpha_3 \cdots (-1)^n \alpha_n\] ділиться на 11.

37. Нехай p₁, p₂, ... , p_s — всі прості числа. Розглянемо число а = p₁ p₂ ⋯ p_s + 1. Воно не ділиться на жодне з чисел p₁, p₂, ... , p_s (лишок від ділення числа а на кожне з них дорівнює 1). З іншого боку, число а розкладається на прості множники (див. задачу 13), тобто ділиться принаймні на одне просте число. Отже, початкове припущення не правильне. Це блискуче доведення належить Евкліду.

38. p = m² − n² ⇔ p = m + n ∧ 1 = m − n. Звідси m = (p + 1)/2, n = (p − 1)/2. Число p непарне, тому числа p + 1 і p − 1 парні, а тому (p + 1)/2 і (p − 1)/2 — цілі.

39 Нехай n = (2k + 1) 2^s, де k — натуральне число. Тоді \(2^n + 1 = (2^{2^s})^{2k+1} + 1 = (2^{2^s} + 1)l\), де l — ціле число, за 1. \[ a^{2k+1} + 1 = (a+1)(a^{2k} - a^{2k-1} + \cdots + a^2 - a + 1).\] 40. Для простих чисел, менших від З0, твердження очевидне. Нехай р — просте число і р > З0. Позначимо через r лишок від ділення р на З0: р = 30q + r. 2, 3 і 5 — дільники числа З0, тому вони не можуть бути дільниками r, бо тоді р не було б простим. Отже, r < З0 і не ділиться на жодне з чисел 2, 3 і 5. Безпосередньо впевнюємось, що такими числами є лише 1, 7, 11, 13, 17, 19, 23, 29.

41. Позначимо: d₁ = НСД (a, b), d₂ = НСД (b, c). a ⋮ d₁ і b ⋮ d₁, тому с = а − bq також ділиться на d₁. Отже, d₁ — спільний дільник чисел b і с. Тому d₂ ⋮ d₁ (див. задачу 6). З іншого боку, b ⋮ d₂ і c ⋮ d₂, тому а = bq + с також ділиться на d₂. Тому d₁ ⋮ d₂. Виходить, що d₁ і d₂ — натуральні числа, які діляться одне на одне. Це означає, що d₁ = d₂.

42. а. Це безпосередньо випливає з визначення найбільшого спільного дільника двох чисел (див. задачу 6).

43. Наслідок задач 41 і 42. НСД(а, b) = НСД(b, r₁) = НСД(r₁, r₂) = ... = НСД(r_{n − 1}, r_n) = НСД(r_n, 0) = r_n.

44. 1) 41; 2) 67; 3) 113; 4) 1.

45. Якщо НСД(а, b) = d, то існують такі цілі числа s₁, s₂ , що as₁ + bs₂ = d. Скоротивши цю рівність на d, матимемо: a₁s₁ + b₁s₂ = 1. Звідси випливає, що a₁ i b₁ взаємно-прості (див. задачу 8).

46.
а) g ⋮ a і g ⋮ b, бо g = ab₁ = ba₁.
б) f ⋮ a ∧ f ⋮ b ⇒ f = as₁ ∧ f = bs₂ ⇒ as₁ = bs₂ ⇒ da₁s₁ = db₁s₂ ⇒ a₁s₁ = b₁s₂ ⇒ s₁ ⋮ b₁, бо a₁ і b₁ взаємно прості (див. задачі 10, 45). Отже, s₁ = qb₁, f = as₁ = a₁b₁dq, а тому f ⋮ a, b, d.

47. Випливає з визначення найменшого спільного кратного двох чисел (див. попередню задачу).

48. [10000/462] = 21, де [z] означає цілу частину z.

49. 1) 123 287; 2) 56 753; 3) 626 603; 4) 114 433.

50. Див. задачі 44 і 3.

51. Якщо натуральне число ділиться на 99, то воно ділиться на 9 і на 11. Якщо число ділиться на 9, то сума його цифр також ділиться на 9. У числа, яке ділиться на 11, сума цифр не може дорівнювати 9 (див. задачу 36). Звідси й випливає твердження задачі.

52. 121 = 11². З’ясуємо спочатку, для яких цілих n число n² + Зn + 5 ділиться на 11. Маємо \[n^2+3n+5 \stackrel{11}{\equiv} n^2+3n+5-11n = (n-4)^2-11 \stackrel{11}{\equiv} (n-4)^2.\] Отже, число n² + Зn + 5 ділиться на 11 тоді й лише тоді, коли (n − 4) ⋮ 11, тобто коли n = 11s + 4, де s — ціле число. Проте у цьому випадку маємо \[ n^2+3n+5 = (11s+4)^2+3(11s+4)+5 = 121s^2 +121s + 33 \stackrel{121}{\equiv} 33.\] Тому жодне з чисел n² + Зn + 5 не ділиться на 121.

53. n + (n + 1) + ⋯ + (n + k) = (2n + k)(k + 1)/2 = 1000. Звідси (2n + k)(k + 1) = 2000. Числа 2n + k і k + 1 мають різну парність. 2000 = 2⁴ · 5³ . Розглянемо спочатку випадок, коли k + 1 — парне число. Оскільки 2n + k у цьому разі буде непарним і, крім того, 2n + k > k + 1, тому k + 1 = 16, звідки k = 15, n = 55. Маємо таку суму: 55 + 56 + ... + 70 = 1000. Розглянувши аналогічно випадок, коли число k + 1 непарне, знайдемо ще два розв’язки: 198 + 199 + 200 + 201 + 202 = 1000 і 28 + 29 + ... + 52 = 1000.

54. Якщо число а² закінчується цифрою 5, то й саме число а має цю властивість: а = 10k + 5. Тому а² = 100k² + 100k + 25 = 100k(k + 1) + 25. Звідси видно, що число а² закінчується цифрами 2 і 5, а його третя від кінця цифра парна, бо k(k + 1) — парне число.

55. Виписати всі дільники числа а і обчислити їхню суму.

56. а³ − b³ = (а — b) (а² + ab + b²), причому число а² + ab + b² непарне.

57. Можна застосувати метод математичної індукції. Число а₀ = 5¹ + 2·3^{1 − 1} + 1 = 8 ділиться на 8. Припустимо, що а_n ділиться на 8. Тоді

а_{n + 1} = 5^{n + 1} + 2·3ⁿ + 1 = 5ⁿ + 2·3^{n − 1} + 1 + 4·(5ⁿ + 3^{n − 1})

також ділиться на 8, бо (5ⁿ + 3^{n − 1}) при будь-якому n ділиться на 2. Згідно з принципом математичної індукції твердження доведено.

58. а = 2⁵ⁿ − 1 = 32ⁿ − 1 = 31 (32^{n − 1} + 32^{n − 2} + ⋯ + 32 + 1).