Подільність і остачі

ПОДІЛЬНІСТЬ І ОСТАЧІ

1.     Доведіть, що добуток трьох послідовних натуральних чисел ділить­ся на 6.

Розв'язання

Серед трьох послідовних натуральних чисел одне ділиться на 3 і при­наймні одне парне. Оскільки числа 2 і 3 взаємно прості, то добуток трьох послідовних натуральних чисел ділиться на 2 ∙ 3 = 6.

2.     Дано р — просте число. Скільки існує натуральних чисел: а) менших за
р і взаємно простих з ним; б) менших за p² і взаємно простих з ним?

Розв'язання

а) Оскільки число р має тільки два дільники: 1 і р, то кожне натуральне
число має тільки один спільний дільник із числом р — це число 1. Отже,
всі числа, менші від р, взаємно прості з р, тому таких чисел р – 1.

б) Кожне число, менше за р² і не, кратне р, не може мати з числом р²
інших спільних дільників, крім 1. Тому чисел, менших за р² і взаємно
простих з ним, має бути р² – 1 – (p – 1) = p² – р. (Тут р – 1 — кількість чисел,
кратних р і менших від р².)

3.     Яке найменше натуральне л, якщо л! ділиться на 990?

Розв'язання

990 ділиться на 11 тому, якщо n! ділиться на 990, то n! повинно діли­тися на просте число 11. Якщо n < 11, то n! не ділиться на 11. Очевидно, що 11! ділиться на 9, на 10 і на 11. А оскільки ці числа взаємно прості, то 11! ділиться на 990. Отже, шукане значення n  = 11.

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

Розв'язання

. Отже,  ділиться на 11. Але ні , ні  не ділиться на 11, оскільки двозначні числа, що діляться на 11, записуються однаковими цифрами.

5.     Чи може число, в десятковому записі якого використано 100 оди­
ниць, 100 двійок, а решта цифр — нулі, бути точним квадратом?

Розв'язання

Ні, не може, бо сума цифр цього числа дорівнює 300. Отже, воно діли­тися на 3. Тоді, щоб число було точним квадратом, воно повинно ділитися і на 9, але на 9 воно не ділиться.

6.     Чи можна всі двоцифрові числа від 32 до 86 включно виписати у пев­ному порядку одне за одним так, щоб дістати запис простого числа?

Розв'язання

В якому б порядку не були записані дані числа, сума цифр, що стояти­муть на непарних місцях, дорівнюватиме 300. Сума ж цифр, які стоятимуть на парних місцях, дорівнюватиме 245. Різниця 300 – 245 = 55 ділиться на 11. Тому дістанемо число, яке ділиться на 11, яке не є простим.

7.     Відомо, що 56а = 65b, причому дій — натуральні числа. Доведіть, що
а+b — складене число.

Розв'язання

65(a + b) = 65a + 65b = 65a + 56a = 121a.

Оскільки, 65 і 121 — взаємно прості числа, то а + b ділиться на 121. Але 121 — складене число. Тому і а +b складене.

Важливі теоретичні відомості

1)    Сума двох довільних натуральних чисел і сума їх остач при діленні на
деяке натуральне число дають однакові остачі.

2)    Добуток двох довільних натуральних чисел і добуток їх остач при
діленні на деяке натуральне число дають однакові остачі.

8.     Знайдіть остачі від ділення: а) 2003∙2004∙2005+2004³ на 7; б) 9¹⁰⁰ на 8.

Розв'язання

а) При діленні на 7 число 2003 дає в остачі 1; 2004 — дає в остачі 2;
2005 — дає в остачі 3. Тому даний вираз при діленні на 7 дасть таку саму
остачу,які1∙2∙3+2³ = 14, тобто 0.

б) При діленні 9 на 8 маємо в остачі 1. Але 1¹⁰⁰ = 1. Тому остача від
ділення 9¹⁰⁰ на 8 дорівнює 1.

9.     Доведіть, що n³ + 2n ділиться на 3 при будь-якому натуральному п.

Розв'язання

Число п при діленні на 3 дає одну з трьох остач: 0, 1, 2. Тому можливі три випадки: п = 3k, п = 3k + 1, п = 3k + 2.

У першому випадку п³ і 2п діляться на 3, а тому і п³+2п також ді­литься на 3.

У другому випадку п³ дає остачу 1, 2п — остачу 2, а 1+2 ділиться на 3.

У третьому випадку п³ дає остачу 2, 2п — остачу 1, а 2+1 ділиться на 3.

Отже, задачу розв'язано.

10.                       Визначте дві останні цифри числа 2^2т.

Розв'язання

Переформулюємо нашу задачу інакше: знайдіть остачу від ділення числа 2²⁰⁰⁴ на 100. Знайдемо послідовність остач від ділення на 100 чисел вигляду 2ⁿ. Вона має вигляд: 2, 4, 8, 16, 32, 64, 28, 56, 12, 24, 48, 96, 92, 84, 68, 36, 72, 44, 88, 76, 52, 4, ... . Бачимо, що, починаючи з другої остачі 4 для п = 22, остачі від ділення повторюються з періодом 20. Оскільки 2004 при діленні на 20 дає остачу 4, то останні дві цифри числа 2²⁰⁰⁴ такі ж, як дві ос­танні цифри числа 2⁴, тобто 1 та 6.

11.                       Доведіть, що квадрати натуральних чисел при діленні на 4 можуть
давати лише остачі 0 або 1.

Розв'язання

Кожне натуральне число можна подати або у вигляді п–2k, або у ви­гляді п=2k+1 (k = 0, 1, 2, ...). У першому випадку n² – 4k² — ділиться на 4. У другому — n² = 4k² + 4k + 1 при діленні на 4 дає в остачі 1.

12.                       Доведіть, що квадрати натуральних чисел при діленні на 3 можуть
давати лише остачі 0 та 1.

Розв'язання

Число п при діленні на 3 може давати остачі 0, 1, 2.

Якщо п = 3k, то п² = 9k² ділиться на 3.

Якщо п = 3k + 1, то п² = 9k² + 6k + 1 дає в остачі 1.

Якщо п = 3k + 2, то п² = 9k² + 12k + 4дає в остачі 1.

13.                       При яких л число 2^п + 3^п + 4^п є точним квадратом?

Розв'язання

При п = 1∙2^п + 3^п + 4^п = 3² є точним квадратом.

Нехай n > 1. Тоді для п = 2k маємо, що 2^п + 3^п + 4^п = 4^k + 3^2k + 4^2k при діленні на 3 дає остачу 2. При n = 2k + 1 число 2^п + 3^п + 4^п = 2∙4^k + 3∙9^k + 4^2k+1 при діленні на 4 дає остачу 3. Отже, при n > 1 число 2^п + 3^п + 4^п не є точним квадратом.

14.                       Доведіть, що р²–q² ділиться на 24, якщо р і q — прості числа, більші від 3.

Розв'язання

Доведемо спочатку, що р² – 1 ділиться на 24. Оскільки 24 = 8 ∙ 3, то доведемо окремо, що р² – 1 ділиться на 8 і ділиться на 3. р² – l = (p – 1)(p + l) — ділиться на 8, як добуток двох послідовних парних чисел.

Оскільки р ≠ 3k, то остача від ділення р² на 3 не дорівнює 0, але дорівнює 1. Отже, р² – 1 ділиться на 3.

Ми довели, що р² – 1 ділиться на 24. Далі р² – q² = (p² – 1) – (q² – 1). За доведеним раніше (р² – 1) ділиться на 24 і (q² – 1) ділиться на 24. Отже, р² – q² ділиться на 24.

15.                       Відомо, що р, р + 10, p + 14 — прості числа. Знайдіть р.

Розв'язання

Якщо р > 3, то р = 3k + 1 або р = 3k + 2.

Якщо р = 3k + 1, то р + 14 = 3k + 15 — ділиться на 3 і не є простим числом.

Якщо р = 3k + 2, то р + 10 = 3k + 12 — ділиться на 3 і теж не є простим числом.

Отже, р ≤ 3, тому р = 3.

16.                       Доведіть, що сума квадратів п'яти послідовних натуральних чисел
не є точним квадратом.

Розв'язання

Серед п'яти послідовних натуральних чисел є або три, або два парних, квадрати яких діляться на 4. Якщо маємо два парних, то непарних чисел буде три і квадрати кожного з них при діленні на 4 дають в остачі 1, а тому сума квадратів всіх п'яти чисел дає в остачі 3.

Якщо ж парних чисел три, то непарних два і сума квадратів усіх п'яти чисел при діленні на 4 дає в остачі 2. Отже, ця сума не може бути точним квадратом.

17.                       Доведіть, що куби натуральних чисел:

а) при діленні на 7 можуть давати лише остачі 0, 1, 6;

б) при діленні на 9 можуть давати лише остачі 0, 1, 8.
Розв'язання

а) Число n при діленні на 7 може давати остачі 0, 1, 2, 3, 4, 5, 6. Тоді
для n³ відповідно остачі такі ж, які і остачі для чисел 0³, 1³, 2³, 3³, 4³, 5³, б³,
тобто 0, 1, 1, 6, 1, 6, 6.

б) Доводиться так само.

18.                       Доведіть, що число 6n³ + 3 не може бути шостим степенем цілого
числа при жодному натуральному n.

Розв'язання

Оскільки k⁶ = (k²)³, то досить довести, що 6n³ + 3 не може бути кубом натурального числа. Розглянемо остачі при діленні 6n³ + 3 на 7. Відомо, що при діленні на 7 число n³ може давати остачі 0, 1, 6.

Якщо n³ дає остачу 0, то 6n³ + 3 дає остачу 3.

Якщо n³ дає остачу 1, то 6n³ + 3 дає остачу 2.

Якщо п³ дає остачу 6, то 6п³ + 3 дає остачу 4.

Отже, жодного разу при діленні 6n³ + 3 на 7 ми не маємо остачу 0, 1, 6. Тому 6n³ + 3 не може бути кубом натурального числа, а тому не може бути й шостим степенем.

19.                       Числа х, у і z — натуральні, причому х² + у² = z². Доведіть, що ху ділиться на 12.

Розв'язання

Якщо з чисел х, у жодне не ділиться на 3, то z² дає остачу 2 при діленні на 3, що неможливо. Отже, кожне з чисел х, уділиться на 3.

Доведемо тепер, що ху ділиться на 4. Зазначимо: 1) квадрат непарного числа при діленні на 8 дає остачу 1; 2) квадрат парного числа, що не ділиться на 4, дає остачу 4; 3) квадрат числа кратного 4 дає остачу 0.

Числа х² і у² не можуть бути обидва непарними, бо тоді їх остачі при діленні на 8, дорівнюють 1, а остача парного числа z² або 4, або 0.

Якщо х² і у² обидва парні, то ху 4.

Залишилося розглянути випадок, коли серед х і у одне число парне, а друге — непарне. Нехай х — парне, у — непарне. Отже, z² — непарне. Тоді при діленні на 8 z² дає остачу 1, у² — остачу 1, а х² — або 0, або 4. Остача 4 неможлива, отже, х² дає остачу 0, а тому х ділиться на 4 і ху ділиться на 4. Маємо: ху ділиться на 4 і на 3. Тому ху ділиться на 12.

20.                       Знайдіть усі натуральні числа х, у, z, для яких виконується рівність
100^x + 211^y = 106^z.

Розв'язання

При z ≥ 3 число 106^z ділиться на 8. Оскільки 105 = 8∙13+1, то при кожно­му натуральному х число 105^х при діленні на 8 дає остачу 1. Оскільки, 211=8∙26+3, а степені трійки при діленні на 8 почергово дають остачі 3 та 1, то і в числах 211^у ці дві остачі теж будуть чергуватися. Тому при z ≤ 3 рів­ність виконуватись не може. При z = 1, очевидно, рівність теж не вико­нується. Перевіримо z = 2. Оскільки 211² > 106², то у = 1. Тоді х = 2. Отже, х = 2, у = 1, z = 2 — єдиний розв'язок задачі.

21.                       Доведіть, що існує нескінченно багато простих чисел.

Розв'язання

Припустимо, що це не правильно. Нехай тоді р₁, р₂, ..., р_п — усі прості числа. Розглянемо число р₁р₂...р_n + 1. Це число не ділиться на жодне з чи­сел р₁, р₂, ..., р_n, а тому не може бути розкладене в добуток простих чисел. Протиріччя доводить, що простих чисел нескінченно багато.

22.                       Доведіть, що існує таке натуральне п, що числа n+1, n+2, n+2004 —
складені.

Розв'язання

Доведемо, що такій умові відповідає число 2005!+1. Зауважимо, що число п! ділиться на кожне з чисел 2, 3. ..., п. Тому для всіх k, для яких 2 ≤ k ≤ п, число n!+k ділиться на k, тобто, є складеним. Отже, якщо вибрати n = 2005, то матимемо 2004 послідовні натуральні числа, серед яких немає жодного простого.

Важливі теоретичні відомості

1)    Якщо цілі числа a і b діляться на d, то їх різниця а – b теж ділиться на d.

2)    Якщо ціле число b та різниця а – b ділиться на d, то й число a = b +(a – b)
також ділиться на d.

3)    Якщо цілі числа a і b діляться на d, то при будь-яких цілих х і у число
ах+by також ділиться на d.

Ці факти — основа алгоритму Евкліда.

Найбільший спільний дільник чисел а і b (a<b) дорівнює найбільшому спільному дільнику числа а та остачі від ділення b на а.

23.                       Знайдіть НСД (1381955; 690713).

Розв'язання

Застосовуємо алгоритм Евкліда

НСД (1381955; 690713) = НСД (690713; 529) = НСД (529; 368) =

= НСД (368; 161) = НСД (161; 46) = НСД (46; 23) = НСД (23; 0) = 23.

24.                       Знайдіть НСД(2n+13; n+7).

Розв'язання

НСД (2n+13; n+7) = НСД(n+7; n+6) = НСД(n+6; 1) = 1.

25.                       Доведіть, що дріб  — нескоротний при жодному натураль­ному п.

Розв'язання

НСД(30n+2; 12n+1) = НСД(12n+1; 6n) = НСД(6n; 1) = 1, тому даний дріб нескоротний.

Задачі для самостійного розв'язування

26.                       Доведіть, що добуток довільних п'яти послідовних натуральних чисел ділиться на 120.

27.                       Скількома нулями закінчується число 2004!?

28.                       Доведіть, що для довільних натуральних чисел т і п справедлива
рівність НСД(m; п)∙НСК(m; п) = тп.

29.                       Доведіть, що п⁵ + 4n ділиться на 5 при довільному натуральному п.

30.                       Числа а і b — натуральні, причому а² + b² ділиться на 21. Доведіть,
що воно ділиться на 441.

31.                       Доведіть, що сума квадратів трьох натуральних чисел, зменшена на
7, не ділиться на 8.

32.                       Якою цифрою закінчується число 777⁷⁷⁷?

33.                       Доведіть, що2222⁵⁵⁵⁵ +5555²²²² ділиться на 7.

34.                       Числа р і 8p² + 1 — прості. Знайдіть р.

35.                       Доведіть, що n⁹ – n³ ділиться на 504 при кожному натуральному п.

36.                       Доведіть, що сума п послідовних непарних натуральних чисел при
п > 1 є складеним числом.

37.                       Доведіть, що число  ділиться на 37 тоді й тільки тоді, коли  ділиться на 37.

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

39.                       Знайдіть НСД(2¹⁰⁰ – 1;2¹²⁰ – 1).

40.                       Знайдіть НСД(111...111; 11..11) — у запису першого числа — 100 одиниць, у запису другого – 60.