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

Как наименьший период степеней связан с делителями показателя

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

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

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

В маршруте Новые структуры целой арифметики · 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. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

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