Математика · объяснение и практика

Как факториал остатков характеризует простое число

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

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

В маршруте Новые структуры целой арифметики · 10 тем

Главная мысль

Для целого n>1 условие (n−1)!≡−1 по модулю n равносильно простоте n. В простом модуле ненулевые остатки объединяются в пары взаимно обратных, кроме единицы и минус единицы.

Точный критерий с факториалом

Теорема Вильсона утверждает не только необходимое условие: если факториал предыдущего числа даёт остаток n−1, то n действительно простое. Область n>1 важна, потому что единица не является простым числом и сравнение по модулю один не различает обычные остатки. Число два включено: 1! имеет требуемый остаток один.

Для нечётного простого p каждый остаток от одного до p−1 имеет единственный мультипликативный обратный. Большинство остатков можно объединить в пары с произведением один. Остаток совпадает со своим обратным только при x²≡1. Тогда p делит (x−1)(x+1), поэтому остаются x≡1 и x≡−1.

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

После сокращения взаимно обратных пар в факториале остаётся произведение 1·(−1). Это и даёт сравнение (p−1)!≡−1. Например, по модулю семь пары 2 и 4, а также 3 и 5 дают единицу; единица и шестёрка остаются самими собой. Полное произведение имеет остаток шесть.

Обратное направление можно доказать без вычисления всех составных случаев. Если n составное, у него есть делитель d с 1<d<n. Число d встречается среди множителей (n−1)!, поэтому делит этот факториал. Оно не может одновременно делить факториал плюс один. Следовательно, n тоже не делит эту сумму, и критерий не выполняется.

Пример

Проверьте условие Вильсона для n=5 и n=6.

Для пяти 4!=24 даёт остаток 4, равный −1 по модулю пять. Для шести 5!=120 даёт остаток ноль, а не пять. Полученные результаты согласуются с простотой пяти и составностью шести.

Почему критерий не обязательно удобен вычислительно

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

Критерий не следует подменять проверкой одной степени по малой теореме Ферма. Успешное сравнение Ферма допускает составные псевдопростые, а факториальное сравнение Вильсона является достаточным. В обоих случаях важно читать логическое направление теоремы: вычислительная похожесть выражений не делает их одинаковыми по силе выводов.

От чтения к действию

А теперь — вы

Пусть целое n>1 удовлетворяет (n−1)!≡−1 по модулю n. Какой вывод обязательно верен?

Частые вопросы

Нужно ли реально вычислять огромное целое значение факториала?

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

Что происходит при n=2?

Условие выполняется: 1!=1≡−1 по модулю два. Поэтому нельзя добавлять требование нечётности ко всем простым из критерия.

Углублённый разбор

Произведение обратимых классов и элементы порядка два

По простому модулю произведение всех ненулевых остатков равно −1. По составному модулю полезно перемножать только обратимые классы: итог определяет число самообратных элементов группы. Получается структурное обобщение спаривания обратных, которое уже не является критерием простоты.

Перед началом: Группа обратимых классов; Векторное пространство над F₂.

Сначала удаляются пары различных обратных

Пусть G — конечная абелева группа. В произведении всех её элементов каждый g с g≠g⁻¹ можно объединить в пару с обратным; пара даёт единицу. Благодаря коммутативности перестановка множителей разрешена. Остаётся произведение элементов T={g:g²=e}, включая e. Для группы единиц modulo n это решения x²≡1 среди обратимых классов, а не все ненулевые остатки составного модуля.

Множество T является подгруппой, поскольку (gh)²=g²h²=e. В аддитивной записи оно является векторным пространством над F₂: каждый элемент равен своему противоположному, а коэффициенты имеют только значения 0,1. Поэтому |T|=2ʳ. Это объясняет, почему число самообратных элементов не может быть произвольным и почему случаи одного, двух и нескольких элементов различаются.

Единственный элемент порядка два остаётся, несколько сокращаются

Если r=0, остаётся только e и произведение равно e. Если r=1, остаются e и один элемент t порядка два, поэтому итог t. Если r≥2, выберем базис T. Каждая базисная координата равна 1 ровно у 2^(r−1) элементов, а это чётное число. Сумма всех координат по модулю 2 нулевая; в мультипликативной записи произведение всех T равно e.

Итак, произведение конечной абелевой группы отлично от единицы ровно тогда, когда имеется единственный элемент порядка два; в этом случае оно равно ему. Для нечётного простого модуля решения x²=1 — только ±1, что возвращает частный случай Вильсона. Для составного модуля могут существовать дополнительные самообратные классы, и результат меняется без противоречия с теоремой для поля.

Продукт единиц и полный факториал отвечают на разные вопросы

По составному модулю необратимые множители полного факториала нельзя сокращать обратными. Поэтому итог произведения только единиц не следует называть факториальным критерием простоты. Например, составной модуль 14 имеет единственный элемент порядка два и произведение единиц −1. Это не делает 14 простым: полный факториал 13! содержит необратимые множители и имеет другой остаток. Для применения структурного правила сначала явно определите перемножаемое множество.

Четыре исключения вместо двух

Условие. Найдите произведение всех обратимых классов по модулю 15 через самообратные элементы и сравните с произведением единиц по модулю 14.

  1. Единицы modulo15 равны 1,2,4,7,8,11,13,14. Различные обратные пары — (2,8) и (7,13); каждая даёт 1.
  2. Самообратные остатки равны 1,4,11,14: их квадраты равны 1 modulo15. Четыре элемента образуют пространство размерности 2, поэтому их произведение равно 1.
  3. Прямо 4·11≡14, затем 14·14≡1. Значит произведение всех единиц modulo15 равно 1, а не −1≡14.
  4. Modulo14 единицы равны 1,3,5,9,11,13. Пары (3,5),(9,11) сокращаются; остаются 1 и 13. Здесь произведение равно 13≡−1, хотя модуль составной.

Ответ. Произведение единиц modulo15 равно 1, modulo14 равно 13.

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

Где легко ошибиться. Не выводите простоту из произведения обратимых классов, равного −1. Критерий Вильсона использует полный факториал, а не сокращённую группу единиц составного модуля.

Проверьте понимание

Чему равно произведение всех обратимых классов по модулю 15?

Вопросы к этой главе

Можно ли применить доказательство к некоммутативной группе?

Спаривание требует свободно переставлять множители, а произведение всех элементов там зависит от порядка. Подгруппа решений g²=e также может не быть замкнутой. Поэтому абелевость в этой формулировке существенна.

Почему −1 не обязательно единственное исключение?

В кольце с делителями нуля равенство (x−1)(x+1)=0 не заставляет один множитель быть нулём. Например, 4²≡1 modulo15, хотя 4 не равен ни 1, ни 14. Полевая аргументация не переносится автоматически.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Saugata Basu: Solutions2, exercise4

    Прочитаны exercise4(a,b) и solution: сумма конечной абелевой группы сводится к 2-кручению и ненулевая только при его размере 2. Формулы доступны в текстовых alt-описаниях изображений; графические формулы отдельно не инспектировались. Перевод на мультипликативную группу единиц и вычисления mod15,14 собственные.

Цифры Лукаса вычисляют биномиальный коэффициент по модулю p

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

Перед началом: Биномиальная формула; Позиционная запись по простому основанию.

Возведение в простую степень упрощает многочлен

В поле F_p все промежуточные биномиальные коэффициенты C(p,j), 0<j<p, равны нулю. Поэтому (1+x)ᵖ=1+xᵖ, а повторение даёт (1+x)^(pⁱ)=1+x^(pⁱ). Если n=Σn_ipⁱ, то (1+x)ⁿ=∏(1+x^(pⁱ))^(n_i) по модулю p.

В каждом множителе степень выбранного локального члена имеет вид k_ipⁱ с 0≤k_i≤n_i<p. Поэтому такие выборы формируют сумму без переносов, то есть единственную позиционную запись k. Сравнение коэффициента xᵏ даёт C(n,k)≡∏C(n_i,k_i) mod p. Если какая-либо k_i>n_i, соответствующий локальный коэффициент равен нулю.

Малые коэффициенты не требуют деления на нулевой факториал

Каждый n_i<p, поэтому n_i!, k_i! и (n_i−k_i)! содержат только обратимые ненулевые элементы поля. Их можно вычислять и обращать по модулю p. Это обходит проблему прямой формулы n!/[k!(n−k)!], где при n≥p факториалы уже обращаются в нуль и деление в поле становится незаконным.

Число цифр растёт логарифмически с n. При фиксированном малом p локальную таблицу C(a,b) для 0≤b≤a<p можно подготовить заранее. Если встретился запрещённый разряд k_i>n_i, дальнейшее умножение не требуется: весь остаток равен нулю. Граничные случаи k=0 и k=n дают произведение единиц.

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

Доказательство использует поле и исчезновение промежуточных коэффициентов именно при простом p. Для составного основания та же цифровая формула в общем случае неверна. Также она не даёт автоматически остаток по p²: там промежуточные коэффициенты уже нельзя просто отбросить.

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

Ненулевой остаток большого коэффициента

Условие. Найдите C(422,256) mod 5 по цифрам. Затем объясните, почему C(422,306) делится на пять, не вычисляя оба больших коэффициента напрямую.

  1. Запись n=422 по основанию пять равна (3142)₅: 3·125+1·25+4·5+2=422.
  2. Для k=256 имеем (2011)₅. По младшим разрядам произведение Лукаса равно C(2,1)·C(4,1)·C(1,0)·C(3,2).
  3. Малые коэффициенты равны 2,4,1,3. Их произведение 24 имеет остаток четыре по модулю пять. Значит, исходный большой коэффициент не делится на пять и имеет конкретный ненулевой класс.
  4. Для 306 получаем (2211)₅. В разряде двадцати пяти цифра k равна двум, а цифра n — единице. Множитель C(1,2)=0 зануляет всё произведение.
  5. Независимое точное вычисление целых биномиальных коэффициентов даёт остатки четыре и нуль. В цифровом решении большие факториалы и недопустимое деление на ноль в F₅ не понадобились.

Ответ. C(422,256)≡4 mod 5; C(422,306)≡0 mod 5. Первый ответ содержит информацию сверх отсутствия делимости на пять.

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

Где легко ошибиться. Не делите n! на k!(n−k)! непосредственно в поле, если факториалы уже равны нулю по модулю p. Цифровое разложение переводит задачу к обратимым малым факториалам.

Проверьте понимание

Каков остаток C(422,256) по модулю пять?

Вопросы к этой главе

Что означает разряд k_i>n_i?

Он делает локальный биномиальный коэффициент нулевым. При переносе вычитания n−k это соответствует невозможности выбрать нужную локальную степень без переноса; весь остаток по p равен нулю.

Можно ли тем же произведением получить остаток по двадцати пяти?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • C. Edmonds, Archive of Formal Proofs: Lucas’s theorem

    Прочитаны описание доказательства через производящие функции и заключительное утверждение Lucas theorem в §2.2.2. Формальный проект локально не запускался. Четырёхразрядные аргументы, оба произведения и независимые проверки построены отдельно; сравнения по квадрату простого не заявляются.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться