Как доказать что число натуральное

Докажите, что при любом натуральном n является составным числом значение выражения: n^2+7n+12

1. Любое натуральное число n можно представить в виде:
n = 2k — 1 или n = 2k, где к — натуральное число.

2. Для нечетных значений n:
n = 2k — 1;
N = (2k — 1)² + 7(2k — 1) + 12;
N = 4k² — 4k + 1 + 14k — 7 + 12;
N = 4k² + 10k + 6;
N = 2(2k² + 5k + 3).

3. Для четных значений n:
n = 2k;
N = (2k)² + 7 * 2k + 12;
N = 4k² + 14k + 12;
N = 2(2k² + 7k + 6).

В обоих случаях N содержит множитель 2, т.е. делится на 2. Следовательно, N — составное число, что и потребовалось доказать.

Сформулируйте и докажите основной закон арифметики натуральных чисел

Основной закон арифметики натуральных чисел состоит из двух частей и формулируется примерно так:

Часть 1. Любое натуральное число, кроме 1, можно представить в виде произведения простых чисел.
Часть 2. Причем данное число всегда будет раскладываться на один и тот же набор простых чисел; может различаться лишь их порядок.

Простое число это натуральное число, которое имеет только два делителя – само себя и 1. Составное число это любое натуральное число, имеющее больше, чем два делителя.

Число 1 не является ни простым, ни составным.

В формулировке первой части основного закона арифметики натуральных чисел говорится, что закон касается всех натуральных чисел (за исключением 1). Это значит, что он относится и к простым числам. Даже если число простое, оно все-равно представимо в виде одного простого числа (самого себя). С другой стороны, тут отсутствует произведение. Можно было бы сказать «в виде произведения 1 и самого себя», но единица не является простым числом, что тоже нарушает определение.

Докажем первую часть закона по отношению к составным числам. Доказательство проведем «от обратного»: допустим, что существуют составные числа, которые нельзя разложить на произведение простых чисел, т. е. в ряде множителей есть другие составные числа.

Любое составное число имеет хотя бы два делителя, отличных от себя самого и единицы. Действительно, обозначим составное число из ряда множителей первого числа как n , его делитель, отличный от 1 и самого n , как m , а получившееся частное как q . Тогда n = mq . Т. е. m и q делители числа n . Причем ни m , ни q не равны самому числу n и 1. Но раз это делители, то они меньше числа n .

Пусть число m было наименьшим составным числом, входящим в ряды разложения других составных чисел. Это число может быть разложено только на простые, т. к. составного числа меньше его просто нет. Отсюда следует, что составное число всегда раскладывается на ряд простых чисел.

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

Допустим, что существует число a , которое можно представить в виде разного набора простых множителей: a = p₁ × p₂ × … × p_m и a = q₁ × q₂ × … × q_n . Поскольку a делится на p₁ , то во втором наборе множителей должно быть точно такое же число (пусть это будет q₂ ). Получаем a ÷ p₁ = p₂ × … × p_m и a ÷ q₂ = q₁ × … × q_n . Подобным образом сократим все одинаковые множители.

Если число a можно было бы представить в виде разного набора простых множителей, то в результате такого сокращения получилось бы число b (из числа a) в одном случае представленное из оставшихся множителей p , а во втором – из оставшихся q . Поскольку мы сократили все, что можно, то оставшиеся множители из разных наборов не равны друг другу. Причем это простые числа. Но перемножение одних простых чисел не может дать такого же результата, как при перемножении других простых чисел. Это следует из особенностей простых и взаимно простых чисел. [не очевидно]

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

Существуют два подхода к определению натуральных чисел — числа, используемые при:

• перечислении (нумеровании) предметов (первый, второй, третий…) — подход, общепринятый в большинстве стран мира (в том числе и в России);
• обозначении количества предметов (нет предметов, один предмет, два предмета…). Принят в трудах Николя Бурбаки, где натуральные числа определяются как мощность конечных множеств.

Отрицательные и нецелые числа натуральными числами не являются.

Множество всех натуральных чисел принято обозначать знаком [math]\mathbb[/math] . Множество натуральных чисел является бесконечным, так как для любого натурального числа найдётся большее его натуральное число.

Формальное определение

Определить множество натуральных чисел позволяют аксиомы Пеано (англ. Peano axioms):

1. [math]1\in\mathbb[/math] ( [math]1[/math] является натуральным числом);
2. Если [math]x\in\mathbb[/math] , то [math]S(x)\in\mathbb[/math] (Число, следующее за натуральным, также является натуральным);
3. [math]\nexists x\in\mathbb\ (S(x) = 1)[/math] ( [math]1[/math] не следует ни за каким натуральным числом);
4. Если [math]S(b)=a[/math] и [math]S(c)=a[/math] , тогда [math]b=c[/math] (если натуральное число [math]a[/math] непосредственно следует как за числом [math]b[/math] , так и за числом [math]c[/math] , то [math]b=c[/math] );
5. Аксиома индукции. Пусть [math]P(n)[/math] — некоторый одноместный предикат, зависящий от параметра — натурального числа [math]n[/math] . Тогда:

Теоретико-множественное определение

Согласно теории множеств, единственным объектом конструирования любых математических систем является множество.

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

• [math]0=\varnothing[/math]
• [math]S(n)=n\cup\left\[/math]

Числа, заданные таким образом, называются ординальными.

Первые несколько ординальных чисел и соответствующие им натуральные числа:

Классы эквивалентности этих множеств относительно биекций также обозначают [math]0, 1, 2, \dots.[/math]

Перечисленные аксиомы отражают наше интуитивные представления о «натуральном ряде».

Операции над натуральными числами

Сложение

Есть два способа определения суммы двух натуральных чисел [math]a\ и\ b[/math] . Если натуральные числа определяют через мощность множества с конечным числом элементов (мощность множества — это количество элементов в нём), тогда целесообразно дать следующее определение суммы:

Пусть [math]N(S)\ — [/math] мощность множества [math]S[/math] . Возьмём два не пересекающихся множества [math]A\[/math] и [math]B,\[/math] причём [math]N(A) = a[/math] и [math]N(B) = b[/math] . Тогда [math]a + b[/math] можно определить как: [math]N ( A ∪ B )[/math] .

Здесь, [math]A ∪ B\ — [/math] это объединение множеств [math]A\ и B\[/math] . В альтернативной версии этого определения множества [math]A\ и\ B[/math] перекрываются и тогда в качестве суммы берётся их дизъюнктное объединение, механизм, который позволяет отделять общие элементы, вследствие чего эти элементы учитываются дважды.

Другое известное определение рекурсивно: Пусть [math]n+\ — [/math] следующее за [math]n[/math] натуральное число, например [math]0+ = 1, 1+ = 2.[/math] Пусть [math]a + 0 = a[/math] . Тогда общая сумма определяется рекурсивно: [math]a + (b+) = (a + b)+[/math] . Отсюда [math]1 + 1 = 1 + 0+ = (1 + 0)+ = 1+ = 2[/math] .

Умножение

Воспользуемся определением натуральных чисел [math]\mathbb[/math] как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств [math]C,\A,\B\[/math] порождённых биекциями, с помощью скобок: [math][C], [A], [B].[/math] Тогда арифметическая операция умножение определяется следующим образом: [math][C] = [A] \cdot [B] = [A \times B];\[/math] где: [math]A \times B=<(a,\ b) \mid a \in A,\ b \in B>\[/math] прямое произведение множеств — множество [math]C,[/math] элементами которого являются упорядоченные пары [math](a,\ b)[/math] для всевозможных [math]a \in A,\ b \in B[/math] . Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.

Вычитание

Воспользуемся определением натуральных чисел [math]\mathbb[/math] как классов эквивалентности конечных множеств. Обозначим классы эквивалентности конечных множеств [math]C , A , B[/math] порождённых биекциями, с помощью скобок: [math][C],\ [A],\ [B].[/math] Тогда арифметическая операция вычитание определяется следующим образом: [math][C] = [A] − [B] = [A \backslash B];\[/math] где [math]A \backslash B = \ < C \in A \mid C \notin B \mid B \subset A \>—\ [/math] разность множеств. Данная операция на классах введена корректно, то есть не зависит от выбора элементов классов, и совпадает с индуктивным определением.

Деление чисел с остатком

Определение:

Если натуральное число [math]n\,[/math] не делится на натуральное число [math]m[/math] , т.е. не существует такого натурального числа [math]k[/math] , что [math]n = m \cdot k[/math] , то деление называется делением с остатком (англ. modulo operation).

Формула деления с остатком: [math]n = m \cdot k + r,[/math] где [math]n\,[/math] — делимое, [math]m\,[/math] — делитель, [math]k\,[/math] — частное, [math]r\,[/math] — остаток, причем [math]0\leqslant r \lt b [/math]

Любое число можно представить в виде: [math]n = 2 \cdot k + r[/math] , где остаток [math]r\, = 0\,[/math] или [math]r\, = 1\,[/math] Любое число можно представить в виде: [math]n = 4 \cdot k + r[/math] , где остаток [math]r\ = 0\,[/math] или [math]r\, = 1\,[/math] или [math]r\, = 2\,[/math] или [math]r\, = 3\,[/math] Любое число можно представить в виде: [math]n = m \cdot k + r[/math] , где остаток [math]r\,[/math] принимает значения от [math]0\,[/math] до [math](m-1)\,[/math]

Основная теорема арифметики

Лемма Евклида

Если простое число [math]p[/math] делит без остатка произведение двух целых чисел [math]x\cdot y[/math] , то [math]p[/math] делит [math]x[/math] или [math]y[/math] .

Пусть [math]x\cdot y[/math] делится на [math]p[/math] , но [math]x[/math] не делится на [math]p[/math] . Тогда [math]x[/math] и [math]p[/math] — взаимно простые, следовательно, найдутся такие целые числа [math]u[/math] и [math]v[/math] , что

Умножая обе части на [math]y[/math] , получаем

Основная теорема арифметики

Каждое натуральное число [math]n\gt 1[/math] представляется в виде [math]n=p_1\cdots p_k[/math] , где [math]p_1,\ldots ,p_k[/math] — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Существование. Пусть [math]n[/math] — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если [math]n[/math] составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, [math]n[/math] тоже является произведением простых чисел. Противоречие.

Принцип индукции, существование наименьшего числа в любом множестве натуральных чисел

Индукция

Формулировка принципа математической индукции:

Пусть имеется последовательность утверждений [math]A_1, A_2, A_3, \ldots[/math] И пусть первое утверждение [math]A_1[/math] верно и мы умеем доказать, что из верности утверждения [math]A_k[/math] следует верность [math]A_[/math] . Тогда все утверждения в этой последовательности верны.

Верность этого метода доказательства вытекает из так называемой аксиомы индукции, пятой из аксиом Пеано, которые определяют натуральные числа. Рассмотрение аксиом Пеано выходит за рамки этой статьи.

Также существует принцип полной математической индукции. Вот его строгая формулировка:

Пусть имеется последовательность утверждений [math]A_1, A_2, A_3, \ldots[/math] . И пусть мы умеем доказать, что из верности утверждения [math]A_1, A_2, A_3, \ldots, A_k[/math] следует верность [math]A_[/math] . Тогда все утверждения в этой последовательности верны.

Существование наименьшего элемента

Аксиому индукции можно заменить на аксиому существования минимума, и доказать аксиому индукции как теорему.

Для любого подмножества натурального ряда всегда существует минимум. Т. е. [math]\forall A \subset \mathbb N, A \ne \varnothing, \exists x \in A: \forall y \in A, x \leqslant y[/math]

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

Если [math]T(n)[/math] истинно при [math]n = 1,[/math] а из того, что оно истинно при всех [math]n \lt k,[/math] следует, что оно истинно и при [math]n = k,[/math] то [math]T(n)[/math] истинно для всех натуральных значений [math]n[/math] .

См. также

• Классы чисел
• Математическая индукция
• Основная теорема арифметики

Источники информации

• ”Математика: Справ, материалы: Кн. для учащих­ся.— М.: Просвещение, 1988.” Авторы: Гусев В. А., Мордкович А. Г. с. 12—13.
• Математическая индукция

Алгоритмы поиска простых чисел

«Самое большое простое число 2 32582657 -1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

Натуральное число называется простым, если оно имеет только два различных делителя: единицу и само себя. Задача поиска простых чисел не дает покоя математикам уже очень давно. Долгое время прямого практического применения эта проблема не имела, но все изменилось с появлением криптографии с открытым ключом. В этой заметке рассматривается несколько способов поиска простых чисел, как представляющих исключительно академический интерес, так и применяемых сегодня в криптографии.

Решето Эратосфена

Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

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

Иллюстрация работы алгоритма из Википедии:

Сложность алгоритма составляет , при этом, для хранения информации о том, какие числа были вычеркнуты требуется памяти.

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до . Это позволяет снизить сложность алгоритма в раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до .

Решето Аткина

Более совершенный алгоритм отсеивания составных чисел был предложен Аткином и Берштайном и получил название Решето Аткина. Этот способ основан на следующих трех свойствах простых чисел.

Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.

Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.

Если n — положительное число, не кратное квадрату простого числа и такое, что . То n — простое, тогда и только тогда, когда число корней уравнения нечетно.

Доказательства этих свойств приводятся в этой статье.

На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все . Для каждой такой пары вычисляется , , и значение элементов массива , , увеличивается на единицу. В конце работы алгоритма индексы всех элементов массива, которые имеют нечетные значения либо простые числа, либо квадраты простого числа. На последнем шаге алгоритма производится вычеркивание квадратов оставшихся в наборе чисел.

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют . При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до , а потребление памяти до .

Числа Мерсенна и тест Люка-Лемера

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

Один из таких методов проверки — тест Люка-Лемера. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида , где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна простое тогда и только тогда, когда p — простое и делит нацело -й член последовательности задаваемой рекуррентно: для .

Для числа длиной p бит вычислительная сложность алгоритма составляет .

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня — , его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.

Теорема Ферма и тест Миллера-Рабина

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство . Доказательство теоремы можно найти на Википедии.

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство , то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

Тест Миллера-Рабина

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения , кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и , тогда для любого a справедливо хотя бы одно из условий:

1. Существует целое число r < sтакое, что

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно .

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое .

Сложность работы алгоритма , где k — количество проверок.

Благодаря быстроте и высокой точности тест Миллера-Рабина широко используется при поиске простых чисел. Многие современные криптографические библиотеки при проверке больших чисел на простоту используют только этот тест и, как показал Мартин Альбрехт в своей работе , этого не всегда оказывается достаточно.

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили все числа до и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.

Тест Люка на сильную псевдопростоту

Последовательности Люка — пары рекуррентных последовательностей , описываемые выражениями:

Пусть и — последовательности Люка, где целые числа P и Q удовлетворяют условию

Найдем такие r, s для которых выполняется равенство

Для простого числа n выполняется одно из следующих условий:

1. n делит
2. n делит для некоторого j < r

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет .

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

Заключение

В зависимости от поставленной задачи, могут использоваться различные методы поиска простых чисел. К примеру, при поиске больших простых чисел Мерсенна, сперва, при помощи решета Эратосфена или Аткина определяется список простых чисел до некоторой границы, предположим, до . Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется .

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен . Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

P.S. Исходники

Реализацию всех описанных алгоритмов на Go можно посмотреть на GitHub.

• Простые числа
• Тест Миллера-Рабина
• Тест Люка
• Числа Мерсенна
• Решето Эратосфена
• Решето Аткина
• Baillie–PSW