Делимость и простые числа

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

Definition

Целое число a делит b, если b равно a, умноженному на некоторое целое число; простое число — это целое число, большее единицы, единственными положительными делителями которого являются единица и само это число. Делимость и простые числа касаются мультипликативного разложения целых чисел и неприводимых строительных блоков этого разложения.

Scope

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

Core questions

• Как алгоритм Евклида вычисляет наибольшие общие делители и приводит к тождеству Безу?
• Почему лемма Евклида требует, чтобы факторизация на простые числа была уникальной?
• Как можно доказать, что существует бесконечно много простых чисел, и что такие доказательства показывают?
• Как распределены простые числа среди целых чисел и как на практике определяется простота?

Key theories

Алгоритм деления и алгоритм Евклида

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

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

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

Бесконечность простых чисел

Классический аргумент Евклида показывает, что ни один конечный список простых чисел не является полным; формула произведения Эйлера для дзета-функции дает аналитическое доказательство и количественно определяет плотность простых чисел через расходимость суммы обратных величин простых чисел.

Clinical relevance

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

History

«Начала» Евклида (около 300 г. до н.э.) уже содержали алгоритм Евклида, лемму Евклида и доказательство бесконечности простых чисел. Решето Эратосфена предоставило первый систематический метод перечисления простых чисел, а работы Эйлера, Лежандра и Гаусса в XVIII и XIX веках переформулировали распределение простых чисел как количественную задачу.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

Является ли единица простым числом?

Нет. Единица исключена по определению, чтобы факторизация на простые числа была уникальной; если бы единица считалась простым числом, каждое число имело бы бесконечно много факторизаций.

Для чего используется тождество Безу?

Оно утверждает, что наибольший общий делитель двух целых чисел является их целочисленной линейной комбинацией, что является основой для вычисления модульных обратных элементов и решения линейных диофантовых уравнений.