Математика · объяснение и практика
Как наименьший период степеней связан с делителями показателя
Как найти наименьший показатель, возвращающий остаток к единице, доказать делимость любого подходящего показателя и не применять порядок к невзаимно простому основанию.

В теме Теория чисел: углубление · Учебная карта
В маршруте Новые структуры целой арифметики · 10 тем
Главная мысль
Порядок a по модулю m≥2 — наименьшее положительное d с aᵈ≡1. Он существует при взаимной простоте a и m; любой другой показатель, дающий единицу, кратен d.
Искать первое возвращение
Возьмём степени двойки по модулю девять. Остатки последовательно равны 2,4,8,7,5,1. Первое возвращение к единице произошло на шестой степени, поэтому порядок равен шести. Нахождение единицы на двенадцатой степени тоже верно, но не устанавливает минимальность. Нужно исключить более ранние положительные показатели.
Если основание и модуль взаимно просты, умножение на основание обратимо среди обратимых остатков. Их конечность заставляет степени повториться, а сокращение общего множителя превращает повторение в степень, равную единице. При отсутствии взаимной простоты это рассуждение теряет обратимость. Например, степени двойки по модулю восемь никогда не возвращаются к единице.
Почему все возвращения кратны первому
Пусть порядок равен d и aᵏ≡1. Разделим k на d: k=qd+r, где 0≤r<d. Тогда aᵏ=(aᵈ)ᑫaʳ≡aʳ. Значит aʳ≡1. Минимальность d запрещает положительный r меньше d, поэтому r=0. Получили d|k, а не просто неравенство d≤k.
Для простого p, не делящего a, малая теорема Ферма даёт a^(p−1)≡1. Следовательно, порядок делит p−1. Это ограничивает поиск делителями известного показателя. Для составного модуля нельзя автоматически использовать m−1 вместо p−1: вывод Ферма был доказан именно при простом модуле.
Пример
Найдите порядок тройки по модулю одиннадцать.
Остатки степеней: 3,9,5,4,1. Первый положительный показатель с единицей равен пяти. Он делит 11−1=10, как и должно быть для простого модуля.
Период и область применения
Порядок определён для остатка основания: замена a на a+m не меняет ни одной степени по модулю. При a≡1 порядок равен одному, а при a≡−1 для модуля больше двух — двум. Эти короткие случаи полезно отделять до длинного вычисления и всегда помнить исключение модуля два, где единица и минус единица совпадают.
Связь с периодом десятичной дроби возникает для знаменателя, взаимно простого с десятью. При делении единицы возвращение остатка соответствует степени десяти, равной единице по знаменателю. Если в знаменателе есть двойки или пятёрки, сначала выделяют непериодическую часть. Порядок десяти по исходному невзаимно простому знаменателю не является корректной заменой этого анализа.
От чтения к действию
А теперь — вы
Частые вопросы
Всегда ли порядок равен p−1 для простого p?
Нет. Он только делит p−1. Например, для тройки по модулю одиннадцать порядок пять, а не десять.
Почему нельзя считать нулевой показатель порядком?
Любое ненулевое основание в нулевой степени даёт единицу. Определение требует положительный показатель, чтобы измерять первое нетривиальное возвращение.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как факториал остатков характеризует простое число
Как произведение всех ненулевых остатков характеризует простой модуль, почему обратные элементы сокращают факториал и чем точный критерий отличается от быстрого теста.
Открыть темуПочему успешная проверка по Ферма ещё не доказывает простоту
Почему прохождение сравнения Ферма не является доказательством простоты, как проверить составной контрпример и отличить свидетельство составности от неудачи найти его.
Открыть тему