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

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

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

Скористаємося властивостями конгруенцій як для додатних цілих чисел так і для від’ємних цілих чисел за модулем 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; 

Простими числами можуть бути числа  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).