Элементарная теория чисел
Элементарная теория чисел изучает целые числа, используя только арифметические и комбинаторные аргументы, формируя аппарат делимости, сравнений и разложения на простые множители, который лежит в основе всей остальной теории.
Definition
Элементарная теория чисел — это раздел теории чисел, занимающийся свойствами целых чисел, устанавливаемыми элементарными методами: индукцией, алгоритмом деления, сравнениями и комбинаторным подсчетом, а не аналитическими или алгебраическими структурными методами.
Scope
Эта область охватывает классическое, самодостаточное ядро теории чисел: отношение делимости и основную теорему арифметики, теорию сравнений и модулярную арифметику, мультипликативные и аддитивные арифметические функции, а также закон квадратичной взаимности. «Элементарная» относится к методу, а не к сложности — результаты получаются без использования комплексного анализа или абстрактного алгебраического аппарата, хотя они и мотивируют оба.
Sub-topics
Core questions
- Как однозначное разложение на простые множители следует из алгоритма деления и алгоритма Евклида?
- Когда сравнение или система сравнений допускает решение, и как подсчитываются решения?
- Как арифметические функции, такие как функция Эйлера и функция Мёбиуса, кодируют мультипликативную структуру?
- Какие целые числа являются квадратичными вычетами по модулю простого числа, и как взаимность связывает условия вычетов для разных простых чисел?
Key theories
- Основная теорема арифметики
- Каждое целое число, большее единицы, однозначно (с точностью до порядка) разлагается на простые множители; это следует из алгоритма деления через лемму Евклида и является структурной основой предмета.
- Теория сравнений
- Работа по модулю n превращает целые числа в конечное кольцо Z/nZ; малая теорема Ферма, теорема Эйлера и китайская теорема об остатках описывают его мультипликативное и структурное поведение.
- Квадратичная взаимность
- Закон Гаусса связывает разрешимость сравнения x в квадрате сравнимо с p по модулю q с разрешимостью x в квадрате сравнимо с q по модулю p, предоставляя эффективный критерий для определения того, когда число является квадратичным вычетом.
Clinical relevance
Конструкции элементарной теории чисел лежат в основе криптографии с открытым ключом (RSA основан на модульном возведении в степень и теореме Эйлера), кодов с исправлением ошибок, хеширования и генерации псевдослучайных чисел, что делает ее практически применяемым уровнем предмета.
History
Самые ранние результаты восходят к «Началам» Евклида (бесконечность простых чисел, алгоритм Евклида). Ферма и Эйлер в семнадцатом и восемнадцатом веках разработали сравнения и функцию Эйлера, а «Арифметические исследования» Гаусса (1801) систематизировали эту область и доказали квадратичную взаимность, определив повестку дня для современной теории чисел.
Key figures
- Euclid
- Pierre de Fermat
- Leonhard Euler
- Carl Friedrich Gauss
Related topics
Seminal works
- hardyWright2008
Frequently asked questions
- Почему она называется «элементарной», если некоторые результаты сложны?
- «Элементарная» относится к используемым методам — арифметике, индукции и сравнениям без комплексного анализа или абстрактной алгебры — а не к сложности доказательств, некоторые из которых весьма замысловаты.
- Является ли элементарная теория чисел все еще активной областью исследований?
- Хотя ее основные результаты являются классическими, элементарные методы остаются центральными в криптографии и комбинаторике, а элементарные доказательства глубоких теорем (такие как элементарное доказательство теоремы о распределении простых чисел Сельбергом и Эрдешем) по-прежнему ценятся.