Натуральне число А=12017 +22017+32017+42017+52017+…+20162017+20172017 поділили на 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
За властивостями
конгруенцій конгруентні числа можна підносити до натурального степеня і конгруенція
залишиться правильною. Тобто
Конгруентні числа 12017 та -20162017 за модулем 2017
Конгруентні числа 22017 та -20152017 за модулем 2017
Конгруентні числа 32017 та -20142017 за модулем 2017
……………………………………………………………………
Конгруентні числа р2017 та (р-2017) 2017 за модулем 2017
……………………………………………………………………
Конгруентні числа 20152017 та -22017
за модулем 2017
Конгруентні числа 2016
та -12017 за модулем 2017
Конгруентні числа 20172017 та 02017 за модулем 2017
Отже, виконаємо
заміну великих степенів на менші у виразі відповідні їм конгруентні числа зі
знаком мінус:
А =12017
+22017+32017+42017+52017+…+20162017+20172017
=
А1= 12017
+22017+32017+42017+52017+…+10072017 +10082017+
+ 10092017 -
-10082017 -10072017- …..
- 22017 -12017+02017
Після взаємного
знищення протилежних доданків, отримаємо
А2=10092017
А2=10092017
Конгруентні числа 10092017 та число А за модулем 2017, тобто у
цих двох чисел будуть рівні остачі при
діленні на 2017.
Скористаємося
малою малою теоремою Ферма.
Так як 2017 просте число та число 1009 та 2017 - взаємно прості, тоді запишемо
В=10092017 =10092017-110091 = 1009201610091
І маємо конгруентні числа 10092016 та число 1 за модулем 2017 згідно теореми Ферма.
Таким чином,
Конгруентні числа 1009
та число 10092017 за модулем 2017, звідки слідує, якщо
А=12017
+22017+32017+42017+52017+…+20162017+20172017 поділили на 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(а4 –b4)=30k;
n5 –n =5k;
n7 –n =7k;
n2 + m2 + r2+1=8k;
(2k+1)2 –(2n-1)2 =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 сума 12000 + 22000+32000 +42000 +…+(р-1)2000
ділиться на просте число р.
Узагальнення цієї задачі на всі прості числа, крім 2. Нехай
р – просте число, більше 2.
Натуральне число
А=1р +2р+3р+4р+5р+…+(р-1)р+рр
при діленні на просте
число р дає натуральну остачу [p/2] +1, де [а] – ціла частина числа.
Найменше натуральне число k називають показником, до якого належить число а за модулем m тоді , коли має місце конгруенція
akº1(mod m),
при цьому k<=j(m) – функції Ейлера і НСД(а; m)=1.
Властивості показників:
1.Якщо числа конгруентні за модулем m, то вони належать до одного і того самого показника.
Якщо a=b(mod m), і ak=1(mod m), то bk=1(mod m),
2.Якщо а належить до показника k за модулем m, то у ряді степенів a0 , a1 , a2 , a3 , ….,ak-1 всі числа не конгруентні одне з одним за модулем m.
3.Якщо а належить до показника k за модулем m, то коенгруенція ak1= аk2 (mod m) має місце тільки тоді, коли k1=k2(mod k).
4.Якщо а належить до показника k за модулем m, то k – буде дільником j(m) функції Ейлера.
4.Якщо а належить до показника k = j(m) за модулем m, то а називають первісним коренем. Числа a0 , a1 , a2 , a3 , …., ak-1 є розв′язками конгруенції хk=1(mod p), тобто k = j(р)=р-1. Отже, первісних коренів шукаємо серед розв′язків конгруенції
хр-1=1(mod p), де р – просте число. Число первісних коренів згідно з теоремою Гауса буде j(р-1).
Цікава інформація.
(modn),
(2)
(3)
(4)
(5)
(6)
Мировая научная общественность считает решение проблемы простых чисел и гипотезы Римана о нулях дзета–функции, тесно связанной с простыми числами, наиболее приотитеными задачами современной науки. Так, Давид Гильберт, выступавший на Международном Парижском математическом конгрессе в 1900 году с подведением итогов развития науки и рассмотрением планов на будущее, включил проблему простых чисел в список 23 проблем, подлежащих решению в новом столетии и способных продвинуть науку далеко вперед. Однако ни проблема простых чисел, ни гипотеза Римана за прошедшие 100 лет не была решена.
На рубеже веков, подводя итоги, американский институт “TheMathematicsInstitute”им. Клея включил гипотезу Римана в одну из 7 приоритетных задач современности.
Гипотеза Римана связана с проблемой распределения простых чисел в натуральном ряде. До сих пор не установлена простая закономерность распределения простых чисел, нет эффективного метода определения простоты числа, нет удовлетворительной формулы количества простых чисел, и вообще, сумма знаний о свойствах, признаках, характере поведения простых чисел является очень скудной и поэтому нет полной картины этого явления. Это связано в первую очередь с их исключительной сложностью.
Теорема о критерии простого числа.
Представляем Вам нашу теорему о критерии простого числа, авторы – Уштенов Еесенбек Рискулович и Мамараимов Мухидин Ташбулатович. Авторское свидетельство зарегистрированно в Комитете по правам интелектуальной собственности Министерства юстиции Республики Казахстан за № 067 от 19.01.2012 год.
Вначале приведем наиболее важные из признаков и свойств простых чисел:
1. Всякое простое число, большее 3, представимо в виде 6k+1или 6k-1, обратное утверждение неверное.
2. Если р-число простое, то р2-1 кратно 24; обратное утверждение неверное.
3. Если р-число простое, то верно сравнение:
(modр), (a,m)=1,что означает, остаток от деление на р равен 1.(Теорема Эйлера). Обратное утверждение неверное.
4. Если р-число простое, то верно сравнение: а р-1≡1(modp), (a,p)=1, и а р≡а (modр). (a,p)=1, чтоозначает, остаток от деленияа р-1 на р равен1, и соответственно остаток от деления а р на р равена.(Малая теорема Ферма), Обратное утверждение неверное.
1. Всякое простое число, большее 3, представимо в виде 6k+1или 6k-1, обратное утверждение неверное.
2. Если р-число простое, то р2-1 кратно 24; обратное утверждение неверное.
3. Если р-число простое, то верно сравнение:
(modр), (a,m)=1,что означает, остаток от деление на р равен 1.(Теорема Эйлера). Обратное утверждение неверное.4. Если р-число простое, то верно сравнение: а р-1≡1(modp), (a,p)=1, и а р≡а (modр). (a,p)=1, чтоозначает, остаток от деленияа р-1 на р равен1, и соответственно остаток от деления а р на р равена.(Малая теорема Ферма), Обратное утверждение неверное.
Есть и другие критерии ( признаки) простоты числа и они является необходимыми условиями, но не достаточными.
Необходимым и достаточным условием простоты числа являются в основном два критерия: теорема Вильсона и метод определения числа, основанный на решете Эротосфена.
1. Теорема Вильсона: Если р-простое число, то имеет место сравнение (р-1)!+1≡0
(modp).(1)
Так же справедлива обратная теорема: Если для целого положительного р имеет место соотношение (1), то р-число простое, т.е. если сумма (р-1)!+1 делится на рбез остатка, то числорявляется простым числом.
Однако!... дело в том, что даже небольших чисел n, число (n-1)!+1 очень большое число!
Если бы мы при помощи указанного критерия захотели бы узнать, например, является ли число 997 простым, то надо было бы проверить делимость числа 996!+1 (число, содержащее 2556 десятичных знаков) на 997. А проверить многозначные числа на простоту даже на современном компьютере не представляется возможным.
2. Также верным способом определение числа на простату является деление определяемого числа х на все простые числа р1; р2; р3 ... pn
. Если в результате этих операций не будет получено ни одного числа без остатка, то это определяемое число х-является простым. Этот метод тоже является точным, но не имеет практического применения. В самом деле, если определяемое число х является 32-х десятизначным, то его необходимо делить на все простые числа, меньшие . Это количество операций будет примерно равно 
что значит большое количество делителей с числами до 16-ти десятичных цифр.
На основании вышеизложенного считаем востребованнойнашутеорему о критерии простого числа.
. Если в результате этих операций не будет получено ни одного числа без остатка, то это определяемое число х-является простым. Этот метод тоже является точным, но не имеет практического применения. В самом деле, если определяемое число х является 32-х десятизначным, то его необходимо делить на все простые числа, меньшие . Это количество операций будет примерно равно что значит большое количество делителей с числами до 16-ти десятичных цифр.На основании вышеизложенного считаем востребованнойнашутеорему о критерии простого числа.
Теорема о критерии простого числа.
Пусть n– нечетное натуральное число. Необходимым и достаточным условием простоты числа nявляется условие выполнения сравнения:
(modn),
Доказательство.
На основании теоремы Вильсона: если имеет место сравнение:
На основании теоремы Вильсона: если имеет место сравнение:
(n-1)!+1≡0 (modn) (1)
то верно утвержение, что число n-простое.
Преобразуем член (n-1)! в следующий вид:
(n-1)!=
=1·2·3·4…·(n-1)=
=1·2·3·4·…·
(2)
Так как, члены, содержащие n, равны нулю по модулю n ,то выражение (1) можно записать в виде:
(3)
Преобразуем последнее выражение (3):
(4)
И окончательно сравнение выглядит так:
(5)
Последнее выражение (5) также можно представить в виде:
(6)
Теорема доказана.
Следствия из теоремы.
Из нашей теоремы можем получить два результата:
1. 
, если p=4k+1,
, если p=4k+1,
Этот результат известен как теорема В.Серпинского.
2. 
если p=4k+3. Второй результатраньше в технической литературе не встречался.
если p=4k+3. Второй результатраньше в технической литературе не встречался.
Последнее сравнение значит, что 
где 
. Отсюда вытекает утверждение:
где . Отсюда вытекает утверждение:
3. 
для простых чисел вида p=4k+3,
для простых чисел вида p=4k+3,
где положительный и отрицательный 
одновременно при одном и том же простом числе место не имеет. Примеры показывают, что для одних простых чисел выполняется =+1 и для других =-1. Критерий при каких простых числах =+1 и при каких =-1 пока нами не установлен, вероятно, что оба случая будут встречаться бесчисленное множество раз.
одновременно при одном и том же простом числе место не имеет. Примеры показывают, что для одних простых чисел выполняется =+1 и для других =-1. Критерий при каких простых числах =+1 и при каких =-1 пока нами не установлен, вероятно, что оба случая будут встречаться бесчисленное множество раз.
Заключение.
Метод основанный на решете Эротосфена предполагает деление данного числа х на все простые числа и потому он не практичен.
и потому он не практичен.
Теорема Лейбница фактически выводится из теоремы Вильсона и повторяет ее.
Теорема В.Серпинского имеет недостаток что она действительна только на числа вида 4k+1, на числа вида 4k+3 она не применима.
В отличие от этих теорем наша теорема критерия простого числа является более прогрессивной, чем все предыдущиеи она отличается от теоремы Вильсона, что в ней в 2 раза меньше сомножителей, и соответственно в 2 раза меньше операций по определению простого числа.
Литература.
- 1. И.М.Виноградов. Основы теории чисел. Издательство «Лань», 2009г.
- 2. Е.К.Титмарш. Теория дзета-функции Римана. Изд. иностранной литературы. Москва, 1953г.
- 3. В.Серпинский. Что мы знаем и что мы не знаем о простых числах. Гос.издат.физ- мат. литературы. Москва, Ленинград. 1963 г.
- 4. Э.Трост. Простые числа. Гос.издат. физ-мат. литературы. Москва 1959г.
