Простое число
-
Определение простых чисел
- Простое число — это натуральное число, большее 1, которое не является произведением двух меньших натуральных чисел.
- Составное число — это натуральное число, большее 1, которое является произведением двух меньших натуральных чисел.
-
История и развитие
- Простые числа изучались с древних времен, начиная с египетских папирусов и древнегреческих математиков.
- Евклид доказал бесконечность простых чисел и фундаментальную теорему арифметики.
- В 1640 году Пьер де Ферма сформулировал малую теорему Ферма.
- В 19 веке Лежандр и Гаусс предположили, что число простых чисел асимптотически стремится к x/log x.
- В 1896 году Адамар и де ла Валле Пуссен доказали теорему о простых числах.
-
Методы проверки простоты
- Пробное деление — медленный метод проверки простоты числа.
- Тест на простоту Миллера–Рабина и тест на простоту AKS — более быстрые методы.
- Для чисел Мерсенна существуют специальные методы проверки простоты.
-
Применение простых чисел
- Простые числа используются в криптографии с открытым ключом.
- В абстрактной алгебре существуют объекты, ведущие себя подобно простым числам.
-
Современные исследования
- В 2004 году теорема Грина–Тао доказала существование сколь угодно длинных арифметических прогрессий простых чисел.
- В 2013 году Итан Чжан доказал существование бесконечно многих простых промежутков ограниченного размера.
-
История классификации простых чисел
- Евклид и другие греческие математики считали 2 простым числом.
- Средневековые исламские математики также не считали 1 числом.
- В Средние века и эпоху Возрождения 1 начали рассматривать как число.
- В XVIII веке Кристиан Гольдбах и Леонард Эйлер обсуждали 1 как простое число.
- В XIX веке многие математики продолжали считать 1 простым числом.
- В начале XX века математики начали считать 1 не простым числом.
-
Элементарные свойства простых чисел
- Уникальная факторизация: каждое число можно записать как произведение простых чисел.
- Фундаментальная теорема арифметики утверждает, что каждое число больше 1 можно разложить на простые множители.
- Простые числа являются «основными строительными блоками» натуральных чисел.
-
Бесконечность простых чисел
- Существует бесконечно много простых чисел.
- Доказательства бесконечности включают теорему Евклида и другие методы.
- Числа, образованные сложением единицы с произведениями наименьших простых чисел, называются числами Евклида.
-
Формулы для простых чисел
- Эффективной формулы для простых чисел не существует.
- Существуют выражения, кодирующие все или только простые числа.
- Примеры формул включают теорему Уилсона и диофантовы уравнения.
-
Открытые вопросы
- Гипотеза Гольдбаха утверждает, что каждое четное число больше 2 можно записать как сумму двух простых чисел.
- Теорема Виноградова утверждает, что каждое достаточно большое нечетное число можно записать как сумму трех простых чисел.
- Гипотезы о пробелах в простых числах включают гипотезу о простых числах-близнецах и гипотезу Полиньяка.
-
Аналитические свойства
- Аналитическая теория чисел изучает простые числа через непрерывные функции и пределы.
- Леонард Эйлер решил базельскую задачу, связанную с дзета-функцией Римана.
- Дзета-функция Римана тесно связана с простыми числами и гипотезой Римана.
-
Распределение простых чисел
- Теорема о простых числах описывает распределение простых чисел в большом количестве.
- Эффективной формулы для этого нет.
- Теорема Дирихле утверждает, что линейные многочлены с относительно простыми целыми числами a и b имеют бесконечно много простых значений.
-
Аналитическое доказательство теоремы Евклида
- Эйлер доказал, что существует бесконечно много простых чисел, используя суммы обратных чисел.
- Сумма обратных чисел простых чисел-близнецов конечна, что делает невозможным использование метода Эйлера для решения гипотезы о двойных простых числах.
-
Количество простых чисел ниже заданной границы
- Функция π(n) определяет число простых чисел, не превышающих n.
- Теорема о простых числах утверждает, что π(n) асимптотически равно n/log n.
- Вероятность того, что случайно выбранное число меньше n простое, обратно пропорциональна количеству цифр в n.
-
Арифметические прогрессии
- Арифметическая прогрессия — это последовательность чисел с одинаковой разницей.
- Теорема Дирихле утверждает, что бесконечная прогрессия с относительно простыми модулем и остатком содержит бесконечно много простых чисел.
- Теорема Грина–Тао показывает, что существуют конечные арифметические прогрессии, состоящие только из простых чисел.
-
Простые значения квадратичных многочленов
- Эйлер отметил, что функция дает простые числа для 1 ≤ n ≤ 40, но составные числа появляются среди более поздних значений.
- Гипотеза Харди–Литтлвуда предсказывает плотность простых чисел среди значений квадратичных многочленов.
- Ни один квадратичный многочлен не может принимать бесконечно много простых значений.
-
Дзета-функция и гипотеза Римана
- Гипотеза Римана утверждает, что нули дзета-функции либо четные отрицательные числа, либо комплексные числа с действительной частью 1/2.
- Произведение Эйлера связывает дзета-функцию с простыми числами и доказывает существование бесконечно многих простых чисел.
- Гипотеза Римана может объяснить асимптотическое распределение простых чисел.
-
Модульная арифметика и конечные поля
- Модульная арифметика изменяет обычную арифметику, используя числа {0, 1, 2, …, n-1} для натурального числа n.
- Деление на все ненулевые числа возможно только при модуле, являющемся простым числом.
- Модульная арифметика по модулю простого числа образует конечное поле.
- Малая теорема Ферма утверждает, что если a ≠ 0 (мод p), то a^p-1 ≡ 1 (мод p).
-
Простые числа и гипотеза Джуги
- Гипотеза Джуги утверждает, что уравнение является достаточным условием для p быть простым.
- Теорема Уилсона утверждает, что p является простым тогда и только тогда, когда факториал (p-1)! соответствует -1 по модулю p.
-
p-адические числа
- p-адический порядок νp(n) целого числа n — это количество копий p в его простой факторизации.
- p-адическое абсолютное значение |q|p рационального числа q определяется как p-νp(q).
- Умножение целого числа на его p-адическое абсолютное значение сводит на нет факторы p в его факторизации.
-
p-адическое расстояние
- Расстояние между двумя рациональными числами может быть измерено по их p-адическому абсолютному значению разности.
- Два числа находятся близко друг к другу, когда их разность делится на большую степень p.
-
p-адические числа и полные поля
- p-адические числа могут быть увеличены до полного поля, как и действительные числа.
- Локально-глобальный принцип позволяет решать задачи с рациональными числами через их p-адические места.
-
Основные элементы в кольцах
- Простые элементы в кольце R — это элементы, отличные от нуля, не имеющие обратной мультипликативной величины и разделяющие произведение двух элементов.
- Неприводимые элементы не являются ни единицей, ни произведением двух других неединичных элементов.
- В кольце целых чисел простые и неприводимые элементы образуют одно и то же множество.
-
Главные идеалы
- Не каждое кольцо является уникальной областью факторизации.
- Простые идеалы обобщают простые элементы и являются важным инструментом в коммутативной алгебре и алгебраической теории чисел.
- Фундаментальная теорема арифметики обобщается на теорему Ласкера-Нетер.
-
Теория групп
- Теоремы Силова и Лагранжа утверждают, что группы простого порядка являются циклическими.
- Теорема Бернсайда утверждает, что группы, порядок которых делится только на два простых числа, разрешимы.
-
Вычислительные методы
- Простые числа используются в криптографических алгоритмах с открытым ключом.
- Современные тесты на первичность и алгоритмы факторизации позволяют быстро определять простые числа.
- Простые числа также используются в вычислениях контрольных сумм, хэш-таблиц и генераторов псевдослучайных чисел.
-
Методы проверки простоты
- Судебное разделение: делит число на каждое целое число от 2 до квадратного корня из числа.
- Проверка только простых чисел в диапазоне.
- Непрактично для больших чисел из-за экспоненциального роста количества тестов.
-
Сита
- Сито Эратосфена: старейший метод создания списка простых чисел.
- Сито Аткина: более асимптотически эффективный метод.
-
Тестирование на первичность
- Вероятностные алгоритмы: тесты с небольшой случайной вероятностью ошибки.
- Тест Соловея–Штрассена: выбирает случайное число и проверяет, делится ли оно на число.
- Гарантированно корректные алгоритмы: тесты с математически доказанной временной сложностью.
-
Специальные алгоритмы и крупнейшее простое число
- Тест Лукаса–Лемера: детерминистически определяет простоту чисел Мерсенна.
- Самое большое известное простое число: число Мерсенна.
-
Целочисленная факторизация
- Задача нахождения простых множителей числа.
- Методы: пробное деление, алгоритм rho Полларда, факторизация эллиптической кривой.
- Алгоритм Шора: раскладывает числа на полиномиальное число шагов на квантовом компьютере.
-
Другие вычислительные приложения
- Криптографические алгоритмы: RSA, обмен ключами Диффи–Хеллмана.
- Хэш-таблицы: метод Картера и Вегмана, квадратичное зондирование.
- Контрольные суммы: международные стандартные книжные номера, Adler-32.
- Генераторы псевдослучайных чисел: линейные конгруэнтные генераторы, смерч Мерсенна.
-
Простые числа в математике
- Простые числа важны в различных разделах математики, таких как теория узлов и теория многообразий.
- Простые числа могут быть использованы для разложения объектов на их простые компоненты.
- Простые числа Ферма связаны с регулярными многоугольниками и полигональными разбиениями.
-
Простые числа в квантовой механике
- Простые числа связаны с энергетическими уровнями квантовых систем.
- Простые числа важны в квантовой информатике благодаря математическим структурам.
-
Простые числа в биологии
- Эволюционная стратегия цикад основана на использовании простых чисел для циклов размножения.
- Многолетние периоды между цветением бамбуковых растений также связаны с простыми числами.
-
Простые числа в искусстве и литературе
- Простые числа оказали влияние на художников и писателей, таких как Оливье Мессиан и Карл Саган.
- Простые числа используются как метафора в литературе, например, в романе Паоло Джордано «Одиночество простых чисел».