ТЕОРЕМИ ПРО ОСТАЧІ

ТЕОРЕМИ ПРО ОСТАЧІ

Теореми про остачі при діленні степенів на натуральні числа.
Варто мати на увазі, що квадрати цілих чисел при діленні на 3 або 4 можуть давати остачі лише 0 та 1, куби при діленні на 9 - лише 0, 1 та 8. (Перевірте це самостійно). Подібні факти в поєднанні з вдалим вибором числа, остачі при діленні на яке ми розглядаємо, часто допомагають розв'язуванню. З допомогою такого вдалого вибору можна доводити, що число не є простим, можна розв'язувати рівняння в цілих числах.

Квадратні лишки

Остачі при діленні квадратів на натуральні числа.

Якщо квадрат натурального числа, тобто, m² = m•m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1;

4, то отримаємо остачі 0, 1;

5, то отримаємо остачі 0, 1, 4;

6, то отримаємо остачі 0, 1, 3, 4;

7, то отримаємо остачі 0, 1, 2, 4;

8, то отримаємо остачі 0, 1, 4;

9, то отримаємо остачі 0, 1, 4, 7;

10, то отримаємо остачі 0, 1, 4, 5, 6, 9;

11, то отримаємо остачі 0, 1, 3, 4, 5, 9;

12, то отримаємо остачі 0, 1, 4, 9;

13, то отримаємо остачі 0, 1, 3, 4, 9, 10, 12;

14, то отримаємо остачі 0, 1, 2, 4, 8, 9;

15, то отримаємо остачі 0, 1,4, 6, 9, 10;

16, то отримаємо остачі 0, 1, 4, 9;

17, то отримаємо остачі 0, 1, 4, 8, 9,15.

Кубічні лишки

Остачі при діленні кубів на натуральні числа.

Якщо куб натурального числа, тобто, m³ = m•m•m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1, 2;

4, то отримаємо остачі 0, 1, 3;

5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

7, то отримаємо остачі 0, 1, 6;

8, то отримаємо остачі 0, 1, 3, 5, 7;

9, то отримаємо остачі 0, 1, 8;

10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.

Четвіркові лишки

Остачі при діленні четвертих степенів на натуральні числа.

Якщо четверту степінь натурального числа, тобто, m⁴ = m•m•m•m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1;

4, то отримаємо остачі 0, 1;

5, то отримаємо остачі 0, 1;

6, то отримаємо остачі 0, 1, 3, 4;

7, то отримаємо остачі 0, 1, 2, 4;

8, то отримаємо остачі 0, 1;

9, то отримаємо остачі 0, 1, 4, 7;

10, то отримаємо остачі 0, 1, 5, 6;

П’ятіркові лишки

Остачі при діленні п’ятих степенів на натуральні числа.

Якщо п’яту степінь натурального числа, тобто, m⁵ = m•m•m•m•m, поділити на:

2, то отримаємо остачі 0, 1;

3, то отримаємо остачі 0, 1, 2;

4, то отримаємо остачі 0, 1, 3;

5, то отримаємо остачі 0, 1, 2, 3, 4;

6, то отримаємо остачі 0, 1, 2, 3, 4, 5;

7, то отримаємо остачі 0, 1, 2, 3, 4, 5, 6;

8, то отримаємо остачі 0, 1, 3, 5, 7;

9, то отримаємо остачі 0, 1, 2, 4, 5, 7, 8;

10, то отримаємо остачі 0, 1, 2, 3, 4, 5; 6; 7; 8; 9.



Задача 1. Знайти остачу від ділення квадрата цілого числа на 5.

Розв’язання:

Квадрати натуральних чисел закінчуються цифрами: 0; 1; 4; 5; 6; 9, то при їх діленні на 5 одержуємо 0, 1 або 4.

Задача 2.

Чи може число виду 1^k+5^m+6ⁿ, де k, m, n – довільні натуральні числа, бути довільним квадратом.

Розв’язання:

Кожний доданок закінчується відповідно цифрами: 1, 5 і 6 і тому їх сума закінчується цифрою 2, а таке число не може бути точним квадратом.

Задача 3.

Довести, що число 53⁵³- 33³³ ділиться на 10.

Розв’язання:

При діленні показників степенів 53 і 33 на 4 в остачі одержуємо в кожному випадку 1.

Отже, остання цифра числа

3⁵³ така сама, як числа 33³³,

бо 53^4•13+1 і 33^4•8+1, отже, остання цифра різниці 0, і ця різниця ділиться на 10.

Задача 4.

Які остачі можуть мати точні квадрати при діленні на 3?

Розв’язання:

(3k ± 1)² = 9k² ± 6k + 1.

(3k)²=9k².

Задача 5.

Які остачі не можуть мати точні квадрати при діленні на 4?

Розв’язання:

(2k)² = 4k².

(2k+1)² = 4k² + 4k + 1.

Відповідь: 2; 3.

Задача 6. Які остачі не можуть мати точні квадрати при діленні на 5?



Розв’язання:

(5k)²=25k² + 0,

(5k ± 1)² = 25k² ± 10k + 1,

(5k ± 2)²= 25k² ± 20k + 4.

Відповідь: 2 і 3.

Задача 7.

Довести, що при будь-якому цілому n число n(n-3)(n²-3n+14) ділиться на 24?

Доведення:

n(n-3)(n²-n-2n+2+12)=n(n-3)(n(n-1)-2(n-1)+12=n(n-3)(n-1)(n-2)+12n(n-3). Це число ділиться на 24, бо:

1. n(n-1)(n-2)(n-3) ділиться на 3 і 8 ділиться на 24.

2. 12n(n-3) ділиться на 12 і 2, бо n(n-3)- просте число, отже, ділиться на 24.

Теорема про остачі

Відмітимо спочатку, що для будь-яких натуральних чисел а і b послідовності а,

а², а³, а⁴, ..., аⁿ, ...

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

Адже за принципом Діріхле в нескінченній послідовності остач, які дають числа аⁿ при діленні на b, обов'язково знайдуться дві однакові остачі.

А якщо а^k та a^s
дають однакові остачі, то однаковими будуть остачі чисел

а^k + 1 та а^s + 1, а^k+2 та а^s+2 і т.д.
І якщо ми знайдемо закон періодичності остач в послідовності а,

а², а³, а⁴, ..., аⁿ, ... ,
то легко зможемо вказати остачу для будь-якого числа аⁿ.

Якщо остача від ділення числа а на b дорівнює с, то остача від ділення числа аⁿ

на b дорівнює остачі від ділення числа cⁿ на b.

Приклад 1. 13 : 5 = 2 (ост. 3), тоді 13ⁿ:5 дає таку саму остачу, як і 3ⁿ:5.

Розв'язання.

1) n = 2, 13²:5 = 169:5 = 33 (ост. 4) і 32:5 = 9:5 = 1 (ост. 4);

2) n = 3, 13³:5 = 2197:5 = 439 (ост. 2) і 33:5 = 27:5 = 5 (ост. 2);

3) n = 4, 13⁴:5 = 28 561:5 = 5712 (ост. 1) і 34:5 = 81:5 = 16(ост. 1);

4) n = 5, 13⁵:5 = 371 293:5 = 74 258 (ост. 3) і 35:5 = 243:5 = 48 (ост. 3).

Приклад 2. Знайти остачу від ділення числа 2222ⁿ на 7.

Розв'язання.

1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).

2) Остача від ділення 2222ⁿ на 7 така сама, як остача від ділення 34 на 7, тобто 4, бо

3⁴:7 = 81:7 = 11 (ост. 4).

Відповідь. 4.

Задача 1. Знайти остачу від ділення числа 2222⁵⁵⁵⁵⁵ на 7.

Розв'язання.

1) Знайдемо остачу від ділення 2222 на 7: 2222 : 7 = 317 (ост. 3).

Остача від ділення 2222⁵⁵⁵⁵ на 7 така сама, як остача від ділення 3⁵⁵⁵⁵ на 7.

Знайдемо остачі від ділення 3ⁿ на 7 для різних значень n:

n=1, 3¹:7 = 3:7 = 0 (ост. 3);

n = 2, 3²:7 = 9:7 = 1 (ост. 2);

n = 3, 3³:7 = 27:7 = 3 (ост. 6);

n = 4, 3⁴:7 = 81:7 = 11 (ост. 4);

n = 5, 3⁵:7 = 243:7 = 34 (ост. 5);

n = 6, 3⁶:7 = 729:7 = 104 (ост. 1);

n = 7, 3⁶:7 = 2187:7 = 312 (ост. 3).

Цикл дорівнює 6.

4) Знайдемо кількість повних циклів у числі 5555. 5555 : 6 = 925 (ост. 5).

925 повних циклів відкидаємо.

Отже, остача відділення 3⁵⁵⁵⁵ на 7 така сама, як від ділення 35 на 7, тобто 5.

Отже, і остача від ділення 2222⁵⁵⁵⁵ на 7 дорівнює 5.

Відповідь. 5.

Задача 2. Знайти остачу від ділення числа 5555²²²² на 7.

Розв'язання.

1) Знайдемо остачу від ділення 5555 на 7: 5555 : 7 = 793 (ост. 4).

Остача від ділення 5555²²²² на 7 така сама, як остача від ділення 4²²²² на 7.

Знайдемо остачі від ділення 4ⁿ на 7 для різних значень n:

n = 1, 4¹:7 = 4:7 = 0 (ост. 4);

n = 2, 4²:7 = 16:7 = 2 (ост. 2);

n = 3, 4³:7 = 64:7 = 9 (ост.1);

n = 4, 4⁴:7 = 256:7 = 36 (ост. 4).

Цикл дорівнює 3.

2) Знайдемо кількість повних циклів у числі 2222. 2222 : 3 = 740 (ост. 2).

740 повних циклів відкидаємо.

Отже, остача від ділення 4²²²² на 7 така сама, як і від ділення 4² на 7, тобто 2.

Отже, і остача відділення 5555²²²² на 7 дорівнює 2.

Відповідь. 2.

Задача 3. Довести, що (2222⁵⁵⁵⁵+5555²²²²) ділиться на 7 без остачі.

Доведення.

Оскільки 2222⁵⁵⁵⁵ при діленні на 7 дає остачу 5, а 5555²²²² при діленні на 7 дає

остачу 2, а сума цих остач 5+2 = 7 ділиться на 7, то (2222⁵⁵⁵⁵+5555²²²²) ділиться

на 7 без остачі, що і треба було довести.

Задача 4. Знайти остачу від ділення числа 7²⁰⁰³ на 10.

Розв'язання.

1) Знайдемо остачу від ділення 7 на 10: 7: 10 = 0 (ост. 7).

2)Знайдемо остачі від ділення 7n на 10 для різних значень n:

n = 1, 7¹:10 = 7:10 = 0 (ост. 7);

n = 2, 7²:10 = 49:10 = 4 (ост. 9);

n = 3, 7³:10 = 343:10 = 34 (ост. 3);

n = 4, 7⁴:10 = 2401:10 = 240(ост. 1);

n = 5, 7⁵ : 10 = 16 807:10 = 1680 (ост. 7).

Цикл дорівнює 4.

3)Знайдемо кількість повних циклів у числі 2003.

2003 : 4 = 500 (ост. 3).

4)500 повних циклів відкидаємо. Отже, остача від ділення 72003 на 10 така сама, як остача від ділення 73 на 10 , тобто 3.

Відповідь. 3.

Задача 5. Якою цифрою закінчується число 7²⁰⁰³?

Розв'язання.

Остача відділення числа 7²⁰⁰³ на 10 є останньою цифрою цього числа.
Тобто число 7²⁰⁰³ закінчується цифрою 3.

Відповідь. 3.

Самостійно виконайте дві наступні вправи.

6.Знайти остачу від ділення числа 2006²⁰⁰⁷ на 3.

7. Якою цифрою закінчується 19²⁰⁰⁹ ?



БЛОК 2

Завдання на дослідження

1. a) Вираз х + 2 ділиться без остачі на 8. Як записати це твердження за допомогою конгруенції? Знайти множину значень х.

б) Вираз х + 2 ділиться без остачі на 3. Як записати це твердження за допомогою конгруенції? Знайти множину значень х.

2. a) Вираз 4х + 3 ділиться з остачею 2 на число 9. Як це записати за допомогою конгруенції? Знайти множину значень х.

б) Вираз 4х + 3 ділиться з остачею 2 на число 5. Як це записати за допомогою конгруенції? Знайти множину значень х.

3. a) Вираз 5х - 1 ділиться з остачею 3 на число 7. Як це записати за допомогою конгруенції? Знайти множину значень х. б) Вираз 5х - 1 ділиться з остачею 3 на число 4. Як це записати за допомогою конгруенції? Знайти множину значень х.

4. a) Вираз а +2 ділиться без остачі на 8. Як записати це твердження за допомогою конгруенції? б) Вираз а +2 ділиться без остачі на 3. Як записати це твердження за допомогою конгруенції?

5. a) Які з чисел 22, 38, 6,-12, -13 конгруентні 9 за модулем 2, 3,7. б) Які з чисел 46, 37, 16, -17, -16 конгруентні 7 за модулем 2, 3, 5, 9.

6. Показати, що числа виду 8k+1, де k=0, 1, 2, ... конгруентні між собою за модулем 8.

7. Довести, що квадрат будь-якого непарного числа конгруентний з одиницею за модулем 8.

8. Показати, що при n непарному, тобто n = 2k±1, число n3 конгруентне 6k+1 за модулем 4.

9. Довести, що якщо 50а+8b+с=0(mod 21), то а+b+8с=0(mod 21).

10. Перевірити конгруенцію 8³⁰=34(mod 55).

11. Перевірити конгруенцію 5²¹=27(mod 77).

12. З яким найменшим натуральним числом конгруентне число

N=8•22•1212•17•23 за модулем 9?

13.Чи вірно, що число 8754 конгруентне 4578 за модулем 9?

14. Чи вірно, що число 5647 конгруентне 22 за модулем 9?

15. Чи вірно, що m³-m+7 конгруентне 7 за модулем 6?

16. Чи вірно, що (2+7)⁵=2⁵+7⁵(mod 5)?