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

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

Это тематический маршрут, а не рецензия на все перечисленные книги. Для содержательного разбора действительно прочитаны законченные разделы авторской электронной версии учебника William Stein и предисловие к четвёртому изданию Mathematical Proofs. Книга Ингама установлена по библиотечной карточке; её содержание здесь не пересказывается. Учебники не переименованы в монографии только ради поискового запроса.

Четыре вопроса, которым нужны разные источники

Запрос о простых числах в других системах счисления содержит важную неоднозначность. Можно спрашивать о том же числе, записанном иначе, а можно — о строке символов, которую заново интерпретируют при другом основании. В первом случае математический объект сохраняется, во втором обычно изменяется. Пока это не уточнено, два правильных вычисления способны дать внешне противоречивые ответы.

Запрос о монографии по простым числам шире. Читателю может понадобиться введение в делимость, теория распределения простых или описание алгоритмических задач. По одному слову «простые» выбрать книгу трудно. Сначала определите, какого результата ждёте: научиться доказывать элементарные утверждения, понять теоретический вопрос или изучить специальный исследовательский метод.

Вопрос о видах теорем также можно понять по-разному. Название «лемма» характеризует роль утверждения в изложении; форма «для каждого» — его логическую структуру; доказательство от противного — способ обоснования. Эти признаки не образуют одну классификацию. Их полезно развести, чтобы не искать книгу с несуществующей универсальной таблицей всех «видов теорем».

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

Три книжных маршрута и точные границы чтения

Авторская страница William Stein называет Elementary Number Theory: Primes, Congruences, and Secrets учебником и прямо сообщает о разрешённом издательством свободном доступе к PDF. На странице говорится о публикации Springer в 2008 году. Однако полученный по её ссылке электронный файл имеет на титуле дату 23 января 2017 года. Эти сведения описывают разные уровни: историю публикации и конкретную прочитанную электронную версию.

В полученном авторском PDF 172 физические страницы PDF. Здесь прочитаны предисловие, раздел о разложении на простые множители, законченные подразделы о бесконечности простых и решете, доказательство десятичного признака делимости на 3 и раздел о двоичном представлении в вычислениях. Остальные главы не объявляются прочитанными, программные примеры Sage не выдаются за выполненные нами в этой системе.

Для методов доказательства использован официальный издательский фрагмент Mathematical Proofs: A Transition to Advanced Mathematics. Титул и оборот устанавливают Gary Chartrand, Albert D. Polimeni, Ping Zhang, четвёртое издание, copyright 2018 и ISBN 978-0-13-474675-3. Целиком прочитано предисловие ix–xv, отдельно — оглавление. Основные главы по этому файлу не прочитаны.

Для специализированного маршрута по распределению простых чисел можно начать с карточки РГБ на книгу А. Э. Ингама: «Распределение простых чисел», перевод и приложение Д. А. Райкова, третье стереотипное издание, Москва: URSS: ЛЕНАНД, 2007, 159, [1] страницы. Это сведения именно выбранной записи. В ней указан электронный ресурс, но фактический переход привёл к сообщению о доступе только внутри РГБ; свободный полный файл не заявляется.

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

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

Число и его позиционная запись — разные понятия

Будем рассматривать неотрицательные целые числа и обычные позиционные системы с целым основанием b ≥ 2. Цифры принимают значения от 0 до b − 1. Значение записи aₖ…a₁a₀ определяется суммой a₀ + a₁b + … + aₖbᵏ. Основание относится к способу представления, а не к новому определению простоты.

Например, 10001 в двоичной системе означает 1 × 2⁴ + 1 = 17. Запись 21 в восьмеричной системе означает 2 × 8 + 1 = 17. Поэтому 17₁₀ = 10001₂ = 21₈. Это три имени одного натурального числа. Его положительные делители от выбора записи не меняются.

Теперь сохраним только строку «17». В десятичной системе она обозначает семнадцать, а в восьмеричной — 1 × 8 + 7 = 15. Получились разные числа: первое простое, второе составное, поскольку 15 = 3 × 5. Противоречия нет: мы изменили не запись одного объекта, а правило чтения фиксированных символов.

В двоичной системе строка «17» вообще не является допустимой записью: цифры 7 там нет. До разговора о простоте нужно проверить корректность исходных данных. Сообщение «неподходящая запись» нельзя заменять ответом «составное число»: в этих условиях натуральное число ещё не задано.

Эту разницу полезно записать в вопросе исследования. «Сохраняется ли простота при переводе того же натурального числа?» и «при каких основаниях данная строка обозначает простое число?» — две задачи. У первой есть общий ответ через определение. У второй значение зависит от основания и состава цифр; иногда уже простая факторизация даёт ограничения.

Например, строка «11» при основании b обозначает b + 1. При b = 2 это 3, при b = 3 это 4, при b = 10 это 11. Из совпадения двух единиц нельзя заключить ни простоту, ни составность для всех оснований. Здесь исследуется семейство разных чисел b + 1, а не одно и то же число в разных записях.

Почему перевод не может изменить простоту: полное доказательство

В принятом здесь определении натуральное число n > 1 является простым, если его положительные делители — только 1 и n. Число 1 не относят ни к простым, ни к составным. В авторской версии Stein это определение дано в начале § 1.1.1; делимость определяется через существование целого множителя, а не через внешний вид цифр.

Утверждение. Если две корректные позиционные записи обозначают одно и то же натуральное число n > 1, то оно простое в одной записи тогда и только тогда, когда простое в другой.

Доказательство. Предположим, что число простое, но при замене его записи стало составным. Составность означала бы существование натуральных u и v, таких что n = uv и 1 < u, v < n. Однако n осталось тем же числом. Следовательно, это же равенство задаёт нетривиальные делители исходного n, что противоречит его простоте. Обратное направление получается перестановкой двух записей. Значит, изменение обозначения при сохранении значения не меняет простоту.

В этом рассуждении важно условие о сохранении значения. Оно не охватывает пример «17» при основаниях 10 и 8, поскольку там получаются 17 и 15. Отсутствие этого условия сделало бы формулировку ложной. Ошибка обнаруживается не сложной теорией, а точным описанием объекта.

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

Для выбранного числа 17 можно дополнительно закончить вычислительную проверку. Если натуральное n составное, запишем n = uv, где 2 ≤ u ≤ v. Тогда u ≤ √n: иначе произведение uv превысило бы n. У числа u есть простой делитель p, причём p ≤ u ≤ √n; этот p делит и n. Поскольку √17 находится между 4 и 5, достаточно проверить простые делители 2 и 3. Число 17 не делится ни на один из них, следовательно, оно простое.

Если √n — целое число, границу включают. Например, для 49 проверки только простых 2, 3 и 5 недостаточно: нужно проверить и 7, поскольку 49 = 7 × 7. Условие «не больше √n» нельзя незаметно заменить строгим неравенством.

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

Почему признаки делимости зависят от основания

Из неизменности делителей не следует неизменность внешней формы школьного признака делимости. Десятичный признак для 3 работает потому, что 10 даёт остаток 1 при делении на 3. Поэтому каждую степень 10 в разложении числа можно заменить единицей при вычислении остатка. Так получаются сумма десятичных цифр и тот же остаток по модулю 3.

Это основание действительно изложено в Proposition 2.1.9 прочитанной версии Stein. Важно не запомнить только сокращённую фразу «сумма цифр», а сохранить условие о системе записи. Число имеет те же делители в любой системе, но удобная операция над цифрами зависит от основания.

Проверим перенос на собственном примере: 1111₂ = 8 + 4 + 2 + 1 = 15. Оно делится на 3, хотя сумма его двоичных цифр равна 4 и на 3 не делится. Значит, механическое применение десятичного правила к двоичным цифрам неверно.

Причина прозрачна: 2 даёт остаток −1 по модулю 3. Поэтому последовательные степени 2 дают чередующиеся остатки 1, −1, 1, −1 и так далее. Для двоичной записи остаток числа по модулю 3 совпадает с чередующейся суммой цифр, начиная справа. У 1111₂ получаем 1 − 1 + 1 − 1 = 0, что согласуется с делимостью 15 на 3.

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

Например, для восьмеричной записи и делителя 7 имеем 8 ≡ 1 по модулю 7. У 21₈ сумма цифр равна 3; само число 17 также даёт остаток 3 при делении на 7. Это ещё одна согласованная проверка, но общность вывода обеспечивается разложением по степеням, а не количеством совпавших примеров.

Теорема, лемма, следствие и форма утверждения

В предисловии Stein объясняет, как именно в своей книге употребляет названия proposition, theorem, lemma и corollary. Это договорённость об устройстве изложения: одни результаты служат промежуточными шагами, другие выступают существенными итогами, третьи следуют из уже полученного. Не следует превращать такую договорённость в универсальную шкалу истинности или строгости.

Лемма не «менее доказана», чем теорема. Её отличие состоит в функции в данном тексте. Утверждение, названное следствием, тоже должно действительно вытекать из указанных оснований. Название результата не исправляет пропущенное условие и не заменяет доказательство.

Рассмотрим фразу «если натуральное число больше 2 и простое, то оно нечётное». Условие «больше 2» обязательно: 2 является простым и чётным. Обратная фраза «каждое нечётное число больше 2 простое» ложна, поскольку 9 = 3 × 3. Исходная теорема и её обращение — разные утверждения.

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

Полезно отдельно проверять отрицание утверждения. Отрицание фразы «для каждого допустимого основания данная строка обозначает простое число» — существование хотя бы одного допустимого основания, при котором значение не простое. Это не фраза «при каждом основании значение составное». У строки «11» основание 3 даёт контрпример всеобщей простоте, но основания 2 и 10 дают простые значения.

Оговорка о допустимости основания здесь существенна. Если строка содержит цифру 7, основания от 2 до 7 не входят в рассматриваемую область для обычной позиционной записи. Нельзя использовать некорректную запись как контрпример к утверждению, сформулированному только для корректных. Сначала задаётся область, затем проверяется заключение.

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

Как различить методы доказательства на одной теме

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

Прямое доказательство. Если a и b делятся на положительное d, то a = du и b = dv для целых u и v. Тогда a + b = d(u + v), поэтому d делит сумму. Мы начали с условия и получили требуемое равенство. Числовая проверка 6 + 9 = 15 при d = 3 лишь иллюстрирует общий аргумент.

Контрапозиция. Утверждение «если квадрат целого n чётный, то n чётный» можно доказать через равносильное «если n нечётный, то его квадрат нечётный». Пусть n = 2k + 1. Тогда n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, то есть квадрат нечётный. Здесь не доказывается обратное утверждение; используется отрицание заключения и отрицание условия исходной импликации.

Доказательство от противного. Предполагают условие и отрицание нужного вывода, затем получают несовместимость с принятыми основаниями. Именно так выше исключена возможность изменения простоты одного и того же числа при замене его записи. Нужно показать конкретное противоречие, а не закончить словами «это невозможно» без объяснения.

Разбор случаев. Для целого n произведение n(n + 1) чётно. Если n чётно, в произведении уже есть множитель 2. Если n нечётно, n + 1 чётно, и такой множитель есть во втором сомножителе. Эти два случая исчерпывают целые числа; не требуется искать третий по виду последних цифр.

Индукция. Чтобы обосновать формулу 1 + 2 + … + n = n(n + 1)/2 для всех натуральных n, проверяют базу n = 1 и переход. Если формула верна для k, прибавление k + 1 даёт k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2. Поэтому утверждение верно для следующего числа. Проверка десяти первых значений не заменяет общий переход.

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

Учебный пример: новое простое число не обязательно равно произведению плюс один

У метода Евклида есть распространённое неверное сокращение: «перемножаем простые, прибавляем единицу и всегда получаем простое». Прочитанный § 1.2.1 Stein специально различает построенное число и его новый простой делитель. Для нашей демонстрации выберем собственный конечный список: 2, 5 и 11. Это не утверждение, что перечислены все простые числа.

Вычислим произведение: 2 × 5 × 11 = 110. Прибавим единицу: N = 111. При делении на 2, 5 и 11 остаток равен 1. Значит, ни один элемент исходного списка не делит N. Однако 111 не простое: 111 = 3 × 37. Число 3 — простой делитель, которого в списке не было.

Для проверки составности достаточно найденного нетривиального произведения. Для вывода о новом простом делителе можно взять 3; доказывать простоту всех сомножителей в выбранном разложении для этого вывода не требуется. Если же мы называем 3 × 37 полным разложением на простые, отдельно проверяем 37: √37 находится между 6 и 7, а делители 2, 3 и 5 ему не подходят.

Теперь общее рассуждение. Для любого конечного списка различных простых p₁, …, pₖ число N = p₁…pₖ + 1 больше 1 и имеет простой делитель q. Если бы q входил в список, он делил бы и N, и N − 1, а значит, их разность 1, что невозможно. Следовательно, найден простой делитель вне списка. Это и исключает существование конечного полного списка простых.

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

Свяжем пример с системами счисления. Строка 111 в десятичной системе означает найденное составное 111. Но 111₂ = 4 + 2 + 1 = 7 — простое число. Это снова разные значения одинаковых символов, а не изменение делимости того же N. Само 111₁₀ в двоичной системе записывается как 1101111₂: 64 + 32 + 8 + 4 + 2 + 1 = 111.

Получен законченный результат: построено N, установлена его составность, найден новый простой делитель, проверено разложение и объяснена роль записи. Числовая демонстрация сопровождает общий аргумент; она не выдаётся за новое исследование распределения простых или авторский результат из недоступной книги Ингама.

Для проверки понимания можно закончить ещё одну небольшую задачу о записи. Фиксируем строку «101» и рассматриваем целые основания b ≥ 2. Её значение равно b² + 1. При b = 2 получаем 5 — простое; при b = 3 получаем 10 — составное. Если b нечётно, b² тоже нечётно, поэтому b² + 1 — чётное число больше 2, а значит, составное. Следовательно, простое значение этой строки возможно только при чётном основании.

Слово «только» задаёт необходимое условие, а не достаточное. При чётном b = 8 значение равно 65 = 5 × 13, то есть составное. Таким образом, получен законченный ответ в заданном масштабе: все нечётные основания исключены, но чётность сама по себе не гарантирует простоту. Полная классификация всех подходящих оснований здесь не заявляется.

Эта задача связывает все четыре направления чтения. Запись задаёт семейство чисел; делимость даёт ограничение; форма импликации отделяет необходимое условие от достаточного; контрпример проверяет ошибочное обращение. Поэтому даже небольшой авторский пример может быть содержательнее списка книг без объяснения, для чего нужна каждая.

Можно поставить и обратный конечный вопрос: при каком основании строка «101» обозначает именно семнадцать? Решаем b² + 1 = 17, то есть b² = 16. Из допустимых положительных оснований подходит только b = 4. Проверка даёт 101₄ = 16 + 1 = 17. Это ещё одна запись того же простого числа, а не пример возникновения нового простого при смене обозначений.

Условие «обозначает именно 17» позволило закончить эту задачу полностью. Без него вопрос о всех основаниях, дающих простое значение b² + 1, существенно шире. Поэтому в обзоре литературы сохраняйте ограничения исходной задачи: пример для одного значения, общий необходимый признак и полная классификация семейства имеют разные масштабы.

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

Как превратить эти задачи в обзор математической литературы

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

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

Рядом с вычислительным примером укажите его роль. Он может иллюстрировать правило, опровергать всеобщее утверждение или проверять конечный результат. Эти роли различны. Пример с 111 опровергает фразу о неизменной простоте произведения плюс один, но не опровергает теорему Евклида.

При выборе издания полезен план работы над литературным обзором. Проверяйте не только автора и год, но и уровень требуемой подготовки. Предисловие Stein прямо предполагает знакомство с основами групп, колец и полей; слово elementary в заглавии не означает, что все главы рассчитаны на человека без алгебраической подготовки.

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

Не переносите библиографический статус с одного источника на другой. Прочитанное предисловие учебника показывает авторский план обучения, а карточка специальной книги — её выходные сведения. Оба источника полезны, но ни один не позволяет оценить все доказательства непрочитанного издания.

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

Рабочий лист: шесть полей для проверки рассуждения

1. Объект и область. Укажите натуральное число, строку цифр или семейство чисел; основание должно быть целым и не меньше 2. Проверьте допустимость каждой цифры.
2. Значение записи. Разложите её по степеням основания. Если переводится то же число, проверьте равенство значений, а не сходство символов.
3. Точное утверждение. Запишите условия, кванторы и направление. Требуется доказать всеобщность, существование, эквивалентность или опровергнуть фразу?
4. Основания доказательства. Назовите определения и уже установленные результаты. Не используйте цель как скрытое предположение.
5. Конечная проверка. Выполните арифметику, укажите границу перебора делителей или предъявите нетривиальное произведение. Не называйте один пример доказательством всеобщности.
6. Источник и предел. Зафиксируйте фактически прочитанную версию и раздел. Отделите её содержание от собственного примера и от вопросов, требующих другой литературы.

По нашему случаю заполнение заканчивается конкретно: 17₁₀, 10001₂ и 21₈ обозначают одно простое число; 17₈ обозначает составное 15; N = 2 × 5 × 11 + 1 = 111 составно, но имеет новый простой делитель 3. Общие выводы подтверждены отдельными рассуждениями, а не только этой строкой ответов.

Частые вопросы о простых числах и математических книгах

Может ли простое число стать составным после перевода в двоичную систему?

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

Почему 17 в десятичной системе простое, а 17 в восьмеричной составное?

Потому что 17₁₀ = 17, а 17₈ = 15 = 3 × 5. Это разные числа. Для того же семнадцати правильная восьмеричная запись — 21₈.

Всегда ли делимость на 3 проверяют суммой цифр?

Обычное правило относится к десятичной записи. В двоичной системе оно не переносится буквально: 1111₂ = 15 делится на 3, хотя сумма цифр равна 4. Нужно учитывать остатки степеней основания.

Лемма менее строгая, чем теорема?

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

Произведение простых плюс один всегда простое?

Нет. В нашем примере 2 × 5 × 11 + 1 = 111 = 3 × 37. Для метода Евклида достаточно простого делителя, которого нет в исходном конечном списке.

Все перечисленные книги — прочитанные монографии?

Нет. Stein и Mathematical Proofs — учебные маршруты с обозначенными границами чтения. Книга Ингама в этом материале установлена по библиотечной карточке; её полный текст не прочитан.

Какие PDF здесь действительно доступны?

Проверены авторская электронная версия Stein и официальный издательский фрагмент Mathematical Proofs. Наличие карточки РГБ на Ингама не означает свободного чтения: фактический переход сообщил об ограничении доступом внутри библиотеки.

Фото: https://kaboompics.com/ / Pexels