Простые числа и делимость с остатком

Опубликовано Четвертнова Татьяна Васильевна вкл 14.11.2017 - 22:51

Автор:

Юрлов Павел

Работа «Простые числа и делимость с остатком» посвящена тестам простоты и делимости чисел с остатком.

Данная тема актуальна с практической точки зрения. Одна из основных тем олимпиадных задач – простые числа. Поэтому необходимо знать способы определения, является ли число простым. Делимость с остатком связана с простыми числами, и задачи, затрагивающие эту тему, встречаются в ЕГЭ.

Автор поставил перед собой цель рассмотреть различные алгоритмы, позволяющие определить, является ли число простым, были доказаны некоторые теоремы.

В работе подробно описывается исследование и на конкретных примерах показывается решение поставленных задач.

Скачать:

Вложение	Размер
yurlov_prostye_chisla.docx	94.57 КБ

Предварительный просмотр:

РЕФЕРАТ

По дисциплине: Математика.

Тема: Простые числа и делимость с остатком.

Выполнил:

Учащийся 10 класса «Б»

Юрлов П. Я.

Подпись

Научный руководитель:

Четвертнова Т. В.

Учитель математики

Оценка

Дата

Подпись

Оглавление

Введение 3

Глава 1. Простое число. Тест простоты. 4

Глава 2. Метод перебора делителей. 5

Глава 3. Тест Ферма. 7

Глава 4. Тест Миллера – Рабина. 10

Глава 5. Китайская теорема об остатках. 12

Глава 6. Решение задач. 13

Заключение. 14

Источники 15

Введение

Простое число — это натуральное число, имеющее ровно два различных натуральных делителя. Натуральные числа больше единицы, не являющиеся простыми, называются составными. Таким образом, все натуральные числа разбиваются на 3 класса: единицу (имеющую один делитель), простые числа (имеющие два делителя) и составные числа (имеющие больше двух делителей). Изучением свойств простых чисел занимается теория чисел.

Проблема:

Определение, является ли число простым.

Актуальность:

Во многих олимпиадах и заданиях ЕГЭ встречаются задачи на простые числа и делимость. Поэтому необходимо знать алгоритмы, позволяющие с той или иной вероятностью определить, является ли число простым. Кроме того, в настоящее время простые числа широко применяются в области защиты информации и криптографии.

Цель исследования:

Рассмотреть тесты простоты и применить их на практике.

Задачи:

Рассмотреть метод перебора делителей.
Доказать малую теорему Ферма и рассмотреть тест Ферма.
Рассмотреть тест Миллера – Рабина.
Рассмотреть китайскую теорему об остатках.
Решить задачи с помощью рассмотренных теорем.

Глава 1. Простое число. Тест простоты.

Самые первые упоминания о простых числах известны у Эвклида (3 в. до н.э.). При этом первый алгоритм нахождения простых чисел был изобретен Эратосфеном (2 в. до н.э.) и известен сейчас под названием решето Эратосфена. Его суть в последовательном исключении из списка целых чисел от 1 до чисел, кратных 2, 3, 5 и другим простым числам. Значительно позже арабский математик ибн ал-Банна предложил делать перебор целых чисел не до , а до $\sqrt{n}$ , что позволило уменьшить количество операций. Недостаток этого метода заключается в том, что вместо проверки заданного числа на простоту он предлагает последовательный перебор всех целых чисел до $\sqrt{n}$ , и поэтому является малоэффективным и требует значительных вычислительных мощностей. В дальнейшем в этой области работали такие математики, как Леонардо Пизанский, известный как Фибоначчи, Ферма, Эйлер, Лежандр, Гаусс и другие.

Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число , позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Таким образом, тест простоты представляет собой только гипотезу о том, что если алгоритм не подтвердил предположение о составности числа , то это число может являться простым с определенной вероятностью. Это определение подразумевает меньшую уверенность в соответствии результата проверки истинному положению вещей, нежели истинное испытание на простоту, которое дает математически подтвержденный результат.

Глава 2. Метод перебора делителей.

Перебор делителей – самый простой способ определить простоту не очень большого числа.

1. Пусть n – проверяемое число.

Согласно этому методу надо разделить число n на все возможные целые делители. При больших значениях n, например, n = 101, проверка каждого делителя займет много времени. Но существуют способы уменьшить количество делителей, которые нужно проверить.

2. Определим, является ли число n четным.

Любое четное число делится на 2. Если число n – четное, то оно является составным. Единственное исключение – число 2.

3. Разделим n на каждое число от 2 до 0,5n.

Так как делитель меньше делимого, то проверка всех делителей меньших 0,5n и больших 2 должна показать, является ли n простым числом. Продолжать делить n на числа, большие 0,5n, нет смысла, так как целого результата мы не получим.

Например, проверим число 11. В этом случае разделим (нацело) 11 на 3, 4, 5. Так как ни одно из этих чисел не делит (нацело) 11, то число 11 – простое число.

4. Чтобы сэкономить время, проверим делители до округленного значения .

Проверка всех делителей от 2 до 0,5n может занять много времени. Например, если необходимо проверить число 103, то придется протестировать следующие числа: 3, 4, 5... и так далее вплоть до 51. Но этого можно избежать, проверяя только делители от 2 до округленного значения

Объяснение этого принципа. Рассмотрим множители 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2, 100 × 1. Обратим внимание, что после пары множителей 10 × 10 все пары множителей повторяются (только множители в этих парах переставлены местами). Поэтому можно игнорировать делители числа n большие, чем

Например, проверим n = 37. Не нужно тестировать все делители от 3 до 18. Вместо этого проверим делители между 2 и округленным значением .

≈ 6,08. Округлим это число до 6.

37 не делится на 3, 4, 5, 6, поэтому оно является простым.

5. Для дальнейшей экономии времени можно тестировать только простые делители.

По определению любое составное число может быть выражено как произведение двух или более простых чисел. Поэтому деление числа n на составной делитель – лишняя операция, повторяющая многократное деление числа n на простые делители. Таким образом, можно еще больше сузить тестируемый ряд делителей.

Это означает, что все четные делители и все делители, кратные простым числам, могут быть опущены.
Например, проверим число 103. ≈ 10. Простые делители от 2 до 10 это 3, 5, 7. Числа 4, 6, 8, 9, 10 можно опустить (9 кратно 3, а все остальные делители – четные числа). Таким образом, мы уменьшили ряд тестируемых чисел до трех.

Делители 3, 5, 7 не делят нацело число 103, поэтому оно является простым.

Глава 3. Тест Ферма.

В 1640 году французский математик Пьер Ферма впервые сформулировал теорему (малая теорема Ферма), которая используется при определении простоты числа. Фактически, тест Ферма служит для определения составных чисел, а не простых. Этот тест с уверенностью определяет, является ли число составным, или определяет, что число «скорее всего» простое. Тест Ферма полезен в случаях, когда перебор делителей непрактичен и когда доступен список чисел, являющихся исключениями из теоремы.

Малая теорема Ферма.

Если p – простое число и — целое число, не делящееся на p, то $a^{p-1}-1$ делится на p, то есть $a^{p-1}\equiv 1 \pmod p$ .

Докажем малую теорему Ферма в другой формулировке.

Если целое число a не кратно простому числу , то $a^{p-1}$ даёт остаток 1 при делении на p.

Лемма.

Для любого простого числа p и целого числа , не кратного , произведения и чисел $1, 2, 3, \ldots , p-1$ при делении на p дают в остатке те же самые числа $1, 2, 3, \ldots , p-1,$ возможно, записанные в некотором другом порядке.

Доказательство леммы.

Произведение k и любого из чисел 1, 2, 3, … , p – 1не кратно p, следовательно, в остатке не может получиться . Все остатки разные. Докажем последнее утверждение от противного. Пусть два произведения ak и bk дают при делении на одинаковые остатки, тогда разность ak – bk = (a – b)k кратна p, что невозможно, поскольку a-b не кратно p. Всего существует p – 1 различных ненулевых остатков от деления на p.

Доказательство теоремы.

Поскольку согласно выше приведенной лемме остатки от деления чисел a, 2a, 3a, ..., (p − 1)a — это с точностью до перестановки числа 1, 2, 3, ... , p − 1, то $a\cdot 2a\cdot 3a\ldots(p-1)a\equiv1\cdot2\cdot3\ldots(p-1) \pmod p$ . Отсюда $a^{p-1}(p-1)!\equiv(p-1)! \pmod p$ . Последнее соотношение можно сократить на (p − 1)!, поскольку все сомножители являются числами, взаимно простыми с основанием p, в результате получаем требуемое утверждение $a^{p-1}\equiv1 \pmod p$ .

Тест Ферма.

Пусть n – проверяемое число.

2. Выберем любое целое число «а» от 2 до n-1 (включительно).

Вычислим an (mod n).

Одним из способов вычисления будет вычислить an, а затем разделить результат на n, а в качестве ответа записать остаток деления

3. Проверим равенство: an a (mod n). Если оно не соблюдено, то n – составное число. Если оно соблюдено, то n, скорее всего, простое число (но не обязательно). Можно повторить тест с разными значениями «а», чтобы удостовериться в правильности ответа. Но есть составные числа, удовлетворяющие условию Ферма при любых значениях «а». Они называются числами Кармайкла.

4. Использование чисел Кармайкла как гарантии правильности ответа. Числа Кармайкла имеют вид (6k + 1)(12k + 1)(18k + 1) для целых значений k, когда каждый делитель является простым.

Пример.

Проверим на простоту число n = 14.

a = 3

314 = 4782969; 4782969 9 (mod 14); 3 9

Число 14 – составное.

Глава 4. Тест Миллера – Рабина.

Тест Миллера – Рабина эффективно определяет, является ли число составным (и лучше обрабатывает исключения, такие как числа Кармайкла).

Пусть n - нечетное число, которое нужно протестировать на простоту.
Запишем n – 1 в виде 2s × d, где d – нечетное число.
Возьмем любое число «а» между 2 и n-1.
Вычислим ad (mod n).

Если ad = 1 или -1 (mod n), то число n проходит тест Миллера – Рабина и, скорее всего, является простым. Однако этот тест, как и тест Ферма, не может определить простоту числа с абсолютной уверенностью.

5. Если n проходит тест Миллера- Рабина, необходимо повторить тест с разными значениями «а», чтобы удостовериться в правильности ответа.

Если n – простое число, оно пройдет тест с любым значением «а». Если n – составное число, не менее трех четвертей значений «а» не пройдут тест. Поэтому тест Миллера – Рабина является более надежным, чем тест Ферма, в котором составные числа Кармайкла проходят тест при любом значении «а».

Пример 1.

Проверим на простоту число 49.

n = 49

n – 1 = 48 = 24 3

a = 7

73 = 343; 343 = 0 (mod 49)

0 1, 0 -1

Число n – составное.

Пример 2.

n = 13

n – 1 = 12 = 22 3

a = 4

43 = 64; 64 = -1 (mod 13)

Число n – простое.

Глава 5. Китайская теорема об остатках.

Китайская теорема об остатках используется, чтобы решить множество уравнений с одной переменной, но различными взаимно простыми модулями, как это показано ниже:

$\tt\parindent0pt x \equiv a_{1} (mod\ m_{1}) x \equiv a_{2} (mod\ m_{2}) … x \equiv a_{k} (mod\ m_{k})$

Китайская теорема об остатках утверждает, что вышеупомянутые уравнения имеют единственное решение, если модули являются взаимно простыми. Также на эту теорему опирается ещё один алгоритм проверки числа на простоту, который мы рассматривать не будем.

Решение.

Найти $M = {m_1} \times {m_2} \times \ldots \times {m_k}$ . Это общий модуль.
Найти M1 = M/m1, M2 = M/m2,…, Mk = M/mk.
Используя соответствующие модули m1, m2,…., mk, найти числа, обратные по модулю M1, M2,…, Mk. Обозначим ее M1-1, M2-1,…, Mk-1.

Обратным к числу a по модулю m называется такое число b, что

a 1 (mod m).

Решение системы уравнений

$x = (a_{1} \times M_{1} \times M_{1}^{-1} + a_{2} \times M_{2} \times M_{2}^{-1}+\dots+ a_{k} \times M_{k} \times M_{k}^{-1}) \mod\ M$

Глава 6. Решение задач.

Задача 1.

Какое число при делении на 3 дает остаток 2, при делении на 5 — остаток 3, а при делении на 7 — остаток 2?

Решение.

По китайской теореме об остатках:

x 2 (mod 3); a1 = 2; m1 = 3

x 3 (mod 5); a2 = 3; m2 = 5

x 2 (mod 7); a3 = 2; m3 = 7

M = 3 5 7 = 105

M1 = M/3 = 35; M1-1 35 1 (mod 3); M1-1 = 2

M2 = M/5 = 21; M2-1 21 1 (mod 5); M2-1 = 1

M3 = M/7 = 15; M3-1 15 1 (mod 7); M3-1 = 1

x = (a1 M1 M1-1 + a2 M2 M2-1 + a2 M3 M3-1) mod M =

= (2 35 3+ 3 21 1 + 2 15 1) mod 105 = 233 mod 105 = 23

Ответ: x = 23.

Задача 2.

Найти остаток от деления 3102 на 101.

Решение.

По малой теореме Ферма:

3100 1 (mod 101)

3100 32 1 32 (mod 101)

3102 9 (mod 101)

Ответ: 9.

Заключение.

Были рассмотрены некоторые тесты простоты: метод перебора делителей, тест Ферма, тест Миллера – Рабина.

Была доказана малая теорема Ферма и рассмотрена китайская теорема об остатках. С помощью обеих теорем были решены задачи.

Источники

http://ru.wikihow.com/%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%82%D1%8C,-%D1%8F%D0%B2%D0%BB%D1%8F%D0%B5%D1%82%D1%81%D1%8F-%D0%BB%D0%B8-%D1%87%D0%B8%D1%81%D0%BB%D0%BE-%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%BC
http://ru.solverbook.com/spravochnik/teoremy/teorema-ferma/
http://e-maxx.ru/algo/reverse_element
https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D1%82%D1%8B
https://ru.wikipedia.org/wiki/%D0%9A%D0%B8%D1%82%D0%B0%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D0%B1_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%B0%D1%85
http://www.intuit.ru/studies/courses/552/408/lecture/9368?page=87.

Распускающиеся бумажные цветы на воде

Рисуем подснежники гуашью

Афонькин С. Ю. Приключения в капле воды

Шелковая горка

Снежная книга