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

Відмітимо спочатку, що для будь-яких натуральних чисел а і b послідовності а, а², а³, а⁴, ..., аⁿ, ... остачі від ділення цих чисел на b будуть періодично повторюватись, починаючи з деякого місця. Адже за принципом Діріхле в нескінченній послідовності остач, які дають числа аⁿ при діленні на b, обов'язково знайдуться дві однакові остачі. А якщо а^k  та a^s дають однакові остачі, то однаковими будуть остачі чисел а^k+1 та а^s+1, а^k+2 та а^s+2 і т.д. І якщо ми знайдемо закон періодичності остач в послідовності а, а², а³, а⁴, ..., аⁿ, ... , то легко зможемо вказати остачу для будь-якого числа аⁿ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Остача від ділення 22225555 на 7 така сама, як остача від ділення 35555 на 7.

Знайдемо остачі від ділення 3n на 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 така сама, як від ділення 3⁵ на 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)Знайдемо остачі від ділення 7ⁿ  на 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 повних циклів відкидаємо. Отже, ос­тача від ділення 7²⁰⁰³ на 10 така сама, як остача від ділення 73 на 10 , тобто 3.

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

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

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

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

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

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

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

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

Відмітимо спочатку, що для будь-яких натуральних чисел а і b послідовності а, а², а³, а⁴, ..., аⁿ, ... остачі від ділення цих чисел на b будуть періодично повторюватись, починаючи з деякого місця. Адже за принципом Діріхле в нескінченній послідовності остач, які дають числа аⁿ при діленні на b, обов'язково знайдуться дві однакові остачі. А якщо а^k  та a^s дають однакові остачі, то однаковими будуть остачі чисел а^k+1 та а^s+1, а^k+2 та а^s+2 і т.д. І якщо ми знайдемо закон періодичності остач в послідовності а, а², а³, а⁴, ..., аⁿ, ... , то легко зможемо вказати остачу для будь-якого числа аⁿ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Остача від ділення 22225555 на 7 така сама, як остача від ділення 35555 на 7.

Знайдемо остачі від ділення 3n на 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 така сама, як від ділення 3⁵ на 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)Знайдемо остачі від ділення 7ⁿ  на 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 повних циклів відкидаємо. Отже, ос­тача від ділення 7²⁰⁰³ на 10 така сама, як остача від ділення 73 на 10 , тобто 3.

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

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

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

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

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

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

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

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