Периоды степеней по модулю — от теории к задаче

Последние цифры, циклы, предпериод, функция Эйлера и максимальный период — простыми словами

В задачах на степени сами числа растут очень быстро, но часто нас интересует только небольшая часть информации о них — например, несколько последних цифр.

Вместо огромных чисел мы будем работать с остатками от деления. Остатков конечное число, поэтому рано или поздно они начинают повторяться. Но повторение бывает устроено по-разному: иногда цикл начинается сразу, а иногда перед ним есть одноразовый «хвост» — предпериод.

В десятичной системе последние две цифры числа определяются остатком при делении на 100:

Последние три цифры — остатком при делении на 1000:

Если система счисления имеет основание C, то последние k цифр числа полностью определяются остатком

Например, последние четыре цифры в системе с основанием 11 означают работу по модулю

По модулю m существует только m возможных остатков:

Поэтому бесконечно получать новые значения невозможно: рано или поздно какой-то остаток встретится снова.

Повторение остатков ещё не означает, что последовательность обязательно вернётся к самому первому элементу.

Пусть модуль имеет вид p^k, где p — простое число, а основание a делится на p.

Например, возьмём модуль 5³ и число

При возведении в степень множители 5 накапливаются:

Поэтому

а дальше остаток навсегда остаётся нулём.

Другое поведение возникает, когда

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

Например, если gcd(a,m)=1 и

то можно сократить на a⁵ и получить

Отсюда важный вывод: для взаимно простых a и m последовательность степеней не имеет одноразового хвоста — она циклична с самого начала.

Если gcd(a,m)=1, то нас интересует первая положительная степень T, для которой

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

Единица впервые появилась на шестой степени, значит

И длина периода равна 6.

Функция Эйлера φ(m) показывает количество чисел от 1 до m, взаимно простых с m.

С 10 взаимно просты

Поэтому

Если gcd(a,m)=1, то

Значит мультипликативный порядок a не может быть больше φ(m). Более того, он делит φ(m):

Если p — простое, то для p^k функция Эйлера вычисляется очень просто:

Почему? Среди чисел от 1 до p^k не взаимно просты с модулем ровно кратные p. Их p^k−1.

Теорема Эйлера говорит, что период не превосходит φ(m). Но для максимума нужно ещё знать, существует ли число с порядком ровно φ(m).

Если

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

Для числа 3:

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

У задачи нет входных данных: C=43 и количество последних цифр k=3 заданы в условии. После аналитического вывода программа просто вычисляет найденную формулу:

p = 43
k = 3

max_period = p ** (k - 1) * (p - 1)

print(max_period)

Результат:

Можно также найти конкретное основание a, которое действительно имеет порядок 77658. Пусть

Если для каждого простого делителя q числа N выполняется

то порядок a равен N.

def prime_divisors(n):
    result = []
    d = 2

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

    if n > 1:
        result.append(n)

    return result


p = 43
k = 3
m = p ** k
N = p ** (k - 1) * (p - 1)

divisors = prime_divisors(N)

for a in range(2, m):
    if a % p == 0:
        continue

    if all(pow(a, N // q, m) != 1 for q in divisors):
        print("Максимальный период:", N)
        print("Пример основания a:", a)
        break

Программа находит, например:

Таким образом, вычислительная проверка подтверждает, что период 77658 не только является верхней границей, но и реально достигается.