Числа виду 1^р +2^р+3^р+4^р+5^р+…+(р-1)^р+р^р

Олімпіадна задача на просте число 2017

Натуральне число  А=1²⁰¹⁷ +2²⁰¹⁷+3²⁰¹⁷+4²⁰¹⁷+5²⁰¹⁷+…+2016²⁰¹⁷+2017²⁰¹⁷ поділили на 2017. Знайти  остачу після такого ділення.

Розв’язання. Два цілих числа х та у називатимемо конгруентними за модулем цілого числа р, якщо цілі числа х та у дають однакову остачу при діленні на число р.
Наприклад. а) Числа 3 та 7 - це конгруентні числа за модулем 2, бо при діленні 3 на 2 і при діленні 7 на 2 отримаємо однакові остачі 1.
б) -1 та 1 -  це конгруентні числа за модулем 2.
в) -4 та 1 -  це конгруентні числа за модулем 5.
г)-2 та 3 -  це конгруентні числа за модулем 5.

Як знаходять конгруентні числа за модулем 6? Для цього можна скласти таблицю:

Z0	Z1	Z2	Z3	Z4	Z5
6n-6	6n-5	6n-4	6n-3	6n-2	6n-1
…	…	…	…	…	…
-12	-11	-10	-9	-8	-7
-6	-5	-4	-3	-2	-1
0	1	2	3	4	5
6	7	8	9	10	11
12	13	14	15	16	17
18	19	20	21	22	23
24	25	26	27	28	29
…	…	…	…	…	…
6n	6n+1	6n+2	6n+3	6n+4	6n+5
Z0	Z1	Z2	Z3	Z4	Z5

Як знаходять конгруентні числа за модулем 5? Для цього можна скласти таблицю:

Z0	Z1	Z2	Z3	Z4
5n-5	5n-4	5n-3	5n-2	5n-1
…	…	…	…	…
-10	-9	-8	-7	-6
-5	-4	-3	-2	-1
0	1	2	3	4
5	6	7	8	9
10	11	12	13	14
15	16	17	18	19
20	21	22	23	24
…	…	…	…	…
5n	5n+1	5n+2	5n+3	5n+4
Z0	Z1	Z2	Z3	Z4

Скористаємося властивостями конгруентних чисел, як для додатних цілих чисел так і для від’ємних цілих чисел за модулем 2017,  тобто (mod 2017) отримаємо таблицю:

0(mod 2017)	1(mod 2017)	2(mod 2017)	3(mod 2017)	4(mod 2017)	…(mod 2017)	р(mod 2017)	…(mod 2017)	2016(mod 2017)
0	-2016(mod 2017)	-2015(mod 2017)	-2014(mod 2017)	-2015(mod 2017)	…(mod 2017)	Р-2017(mod 2017)	…(mod 2017)	-1(mod 2017)

Конгруентні числа  1 та -2016  за модулем 2017

Конгруентні числа  2 та -2015  за модулем 2017

Конгруентні числа  3 та -2014  за модулем 2017

……………………………………………………………………

Конгруентні числа  р та р-2017за модулем 2017

……………………………………………………………………

Конгруентні числа  2015 та -2  за модулем 2017

Конгруентні числа  2016 та -1  за модулем 2017

Конгруентні числа  2017 та 0 за модулем 2017

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

Конгруентні числа  1²⁰¹⁷ та -2016²⁰¹⁷  за модулем 2017

Конгруентні числа  2²⁰¹⁷ та -2015²⁰¹⁷  за модулем 2017

Конгруентні числа  3²⁰¹⁷ та -2014²⁰¹⁷  за модулем 2017

……………………………………………………………………

Конгруентні числа  р²⁰¹⁷ та (р-2017) ²⁰¹⁷ за модулем 2017

……………………………………………………………………

Конгруентні числа  2015²⁰¹⁷ та -2²⁰¹⁷  за модулем 2017

Конгруентні числа  2016 та -1²⁰¹⁷  за модулем 2017

Конгруентні числа  2017²⁰¹⁷ та 0²⁰¹⁷ за модулем 2017

Отже, виконаємо заміну великих степенів на менші у виразі відповідні їм конгруентні числа зі знаком мінус:

А =1²⁰¹⁷ +2²⁰¹⁷+3²⁰¹⁷+4²⁰¹⁷+5²⁰¹⁷+…+2016²⁰¹⁷+2017²⁰¹⁷ =

А1= 1²⁰¹⁷ +2²⁰¹⁷+3²⁰¹⁷+4²⁰¹⁷+5²⁰¹⁷+…+1007²⁰¹⁷  +1008²⁰¹⁷⁺

 + 1009²⁰¹⁷ -

 -1008²⁰¹⁷ -1007²⁰¹⁷- ….. - 2²⁰¹⁷ -1²⁰¹⁷+0²⁰¹⁷  

Після взаємного знищення протилежних доданків, отримаємо
А2=1009²⁰¹⁷ 

Конгруентні числа  1009²⁰¹⁷ та  число А  за модулем 2017, тобто у цих  двох чисел будуть рівні остачі при діленні на 2017.

Скористаємося малою  малою теоремою Ферма.

 Так як 2017 просте число та число 1009 та 2017 - взаємно прості, тоді запишемо

В=1009²⁰¹⁷ =1009^2017-11009^{1 =} 1009²⁰¹⁶1009¹  

І маємо конгруентні числа  1009²⁰¹⁶ та  число 1  за модулем 2017 згідно теореми Ферма.

Таким чином,

Конгруентні числа  1009 та  число 1009²⁰¹⁷  за модулем 2017, звідки слідує,   якщо

А=1²⁰¹⁷ +2²⁰¹⁷+3²⁰¹⁷+4²⁰¹⁷+5²⁰¹⁷+…+2016²⁰¹⁷+2017²⁰¹⁷ поділили на 2017 то остача 1009.

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

Відомі факти для подільності  чисел.

Усі натуральні  числа можна записати так:  а)   5k-2,  5k-1, 5k, 5k+1, 5k+2;  б)  6k-3,  6k-2,  6k-1, 6k, 6k+1, 6k+2; 

Усі прості числа(починаючи з 5) можна  записати у вигляді:    6k-1 та 6k+1,  якщо k  – натуральне  число.

аb(а ± b)=2k – це парне число.

аb(а⁴ –b⁴)=30k; 

n⁵ –n =5k; 

n⁷ –n =7k;   

n² + m² + r²+1=8k;

(2k+1)² –(2n-1)² =8k;

n(n+1)= 2k, тобто, добуток двох послідовних цілих чисел завжди парне число;

(n+2)(n+1)n = 3k, тобто, добуток трьох послідовних цілих чисел завжди ділиться на 3 націло;

(n-1)n(n+1) = 6k, тобто, добуток трьох послідовних цілих чисел завжди ділиться на 6 націло;

(n-1)n(n+1)(n+2) = 6k тобто, добуток трьох послідовних цілих чисел завжди ділиться на 6 націло;

(n-2)(n-1)n(n+1)(n+2) = 2∙3∙4∙5k=120k, тобто, добуток п’яти послідовних цілих чисел завжди ділиться на 120 націло.

Для всіх простих чисел р> 2000 сума  1²⁰⁰⁰ + 2²⁰⁰⁰+3²⁰⁰⁰ +4²⁰⁰⁰ +…+(р-1)²⁰⁰⁰

ділиться на просте число р.

Узагальнення цієї задачі на всі прості числа, крім 2. Нехай р – просте число, більше 2.

Натуральне число

А=1^р +2^р+3^р+4^р+5^р+…+(р-1)^р+р^р

при діленні на просте число  р дає натуральну остачу [p/2] +1,  де [а] – ціла частина числа. 

Найменше натуральне число  k називають показником, до якого належить число а за модулем m  тоді , коли має місце конгруенція 

a^kº1(mod m),

при цьому k<=j(m) – функції Ейлера і НСД(а; m)=1.

Властивості показників:

1.Якщо числа конгруентні за модулем m, то вони належать до одного і того самого показника.

Якщо  a=b(mod m),    і    a^k=1(mod m), то  b^k=1(mod m),

2.Якщо а належить до показника  k за модулем m, то у ряді степенів  a⁰ , a¹ , a² , a³ , ….,a^k-1 всі числа не конгруентні одне з одним за модулем m.

3.Якщо а належить до показника  k за модулем m, то коенгруенція  a^k1= а^k2 (mod m) має місце тільки тоді, коли k1=k2(mod k).

4.Якщо а належить до показника  k за модулем m, то k – буде дільником j(m) функції Ейлера.

4.Якщо а належить до показника  k = j(m) за модулем m, то а називають первісним коренем.  Числа a⁰ , a¹ , a² , a³ , …., a^k-1 є розв′язками конгруенції  х^k=1(mod p),  тобто k = j(р)=р-1. Отже,  первісних коренів шукаємо серед розв′язків конгруенції

х^р-1=1(mod p),  де р – просте число. Число первісних коренів згідно з теоремою Гауса буде  j(р-1).