ПЕРИОДЫ СТЕПЕНЕЙ ПО МОДУЛЮ

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

---

Рассмотрим степени положительного целого числа a:

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

---

В позиционной системе счисления число имеет вид

Если нас интересуют только последние k цифр, все слагаемые начиная с C^k можно отбросить: они делятся на C^k. Поэтому последние k цифр полностью определяются величиной

Например, если C = 47 и выводятся последние четыре цифры, то мы изучаем не огромные числа aⁿ, а только

---

Период T — это число шагов, через которое последовательность остатков начинает повторяться в том же порядке:

Если a взаимно просто с m, число aⁿ можно сократить по модулю m. Тогда условие периода превращается в

Минимальное положительное T, для которого это выполняется, называется мультипликативным порядком числа a по модулю m:

---

Если gcd(a,m) = 1, число a принадлежит группе обратимых остатков по модулю m. Количество таких остатков равно функции Эйлера φ(m).

Теорема Эйлера утверждает:

Отсюда порядок a обязательно делит φ(m):

Следовательно,

---

Если для некоторого g выполняется

то g называется первообразным корнем по модулю m.

Например, по модулю 7:

a	Степени до возвращения к 1	Порядок
2	1 → 2 → 4 → 1	3
3	1 → 3 → 2 → 6 → 4 → 5 → 1	6

Поскольку φ(7) = 6, число 3 является первообразным корнем по модулю 7.

---

Для простого p функция Эйлера от степени p имеет особенно простой вид:

Так как по модулю p^k существует первообразный корень, максимальная длина периода равна

Модуль равен 73³. Поэтому

---

Пусть p — простое. Возможный максимальный порядок равен p - 1. Разложим p - 1 на простые множители и выпишем только различные простые делители q.

Число g является первообразным корнем по модулю p тогда и только тогда, когда для каждого такого q

Если порядок g был бы собственным делителем числа p - 1, то число (p - 1) / ord_p(g) имело бы хотя бы один простой делитель q. Тогда уже степень (p - 1) / q дала бы единицу. Поэтому проверять все делители p - 1 не нужно.

Имеем

Различные простые делители — только 2 и 3. Для g = 5 достаточно проверить две степени:

Проверка	Остаток	Вывод
536 mod 73	72	не 1
524 mod 73	8	не 1

Значит ord₇₃(5) = 72, то есть 5 — первообразный корень по модулю 73.

Чтобы подняться от p к p², проверяют ещё одно условие:

Для g = 5:

Поэтому 5 остаётся первообразным корнем по модулям 73², 73³, ...

---

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

В циклической группе порядка N количество элементов порядка ровно N равно φ(N). Для модуля p^k группа обратимых остатков имеет порядок

Следовательно, количество первообразных корней, а значит и количество значений a с максимальным периодом, равно

Модуль:

Максимальный период:

Разложение:

Количество значений a с таким периодом:

---

Если нужно решить задачу программно, перебирать все значения a и строить для каждого последовательность степеней невыгодно. Чисел почти 4,9 миллиона, а максимальный период сам имеет длину почти 4,8 миллиона.

Чтобы вычислить φ(n), достаточно разложить n на простые множители. Для каждого различного простого делителя p используется формула

def phi(n):
    result = n
    p = 2

    while p * p <= n:
        if n % p == 0:
            # p — один из простых делителей n
            while n % p == 0:
                n //= p

            result -= result // p

        p += 1

    # если после перебора остался простой множитель
    if n > 1:
        result -= result // n

    return result

C = 47
k = 4

m = C ** k

# максимальный возможный период
max_period = phi(m)

# число элементов максимального порядка
answer = phi(max_period)

print(m)
print(max_period)
print(answer)

Программа выведет:

4879681
4775858
2235508

Следовательно, программно получаем тот же ответ:

Если требуется не посчитать количество таких чисел, а проверить конкретное a, можно воспользоваться критерием максимального порядка. Пусть N = φ(m), а q — различные простые делители N. Тогда a имеет порядок N, если

для каждого простого делителя q числа N.

def prime_divisors(n):
    divisors = []
    p = 2

    while p * p <= n:
        if n % p == 0:
            divisors.append(p)
            while n % p == 0:
                n //= p
        p += 1

    if n > 1:
        divisors.append(n)

    return divisors


def has_max_period(a, m):
    N = phi(m)

    for q in prime_divisors(N):
        if pow(a, N // q, m) == 1:
            return False

    return True

Здесь pow(a, b, m) вычисляет a^b mod m быстрым возведением в степень и не создаёт огромное число a^b.

---

Введите нечётное простое основание p и число выводимых цифр k. Калькулятор покажет модуль p^k, максимальный период, количество значений a с максимальным периодом и один конкретный первообразный корень.

---