Триша Тройкин, Петя Пятаков и Сёма Семак пытаются сконструировать собственный генератор псевдослучайных чисел.
Для этого они взяли натуральные числа a и m (одни и те же у всех троих) и выстраивают последовательность по правилу:

x_n+1 = x_n*a (mod m).

Начав с некоторого x₁, Триша посчитал x₂, x₃ и x₄. Но x₄ оказалось равно x₁.
Тогда он взял другое (не встречавшееся ранее) число в качестве x₁. Но последовательность опять зациклилась на третьем шаге. Треья попытка привела Тришу к тому же результату.

Петя совершил пять попыток подобрать x₁. Но всякий раз получал новые циклы длины 5.
Наиболее упорным оказался Сёма. Он совершил семь попыток. И получил семь циклов длины 7.

При каком наименьшем m могла возникнуть такая ситуация?

Решение

Умножение на фиксированное натуральное число с последующим приведением по модулю m задает на множестве классов вычетов по модулю m отображение в себя, т. е. структуру унара (множества с одной унарной операцией). Назовем класс b циклическим, если найдется натуральное n такое, что b*aⁿ == b mod m (1). Наименьшее натуральное n, при котором выполняется сравнение (1) назовем периодом элемента b.

Обозначим: d = (a,m) = p₁^{d₁}*...*p_k^{d_k}, P = p₁*...*p_k.

Тогда a = p₁^{a₁}*...p_k^{a_k}*a', m = p₁^{m₁}*...p_k^{m_k}*m',

b = p₁^{b₁}*...*p_k^{b_k}*b', где (a',P) = (m',P) = (b',P) = 1,

a_i, m_i - натypальные, b_i -целые неотpицательные.

Пyсть, далее, mm = m'/(m',b), T(b) - пеpиод b.
Доказательства следyющих лемм почти очевидны.

**Лемма 1.**
b - циклический тогда и только тогда, когда b_i ≥ m_i для всех i.

**Лемма 2.**
T(b) = ord_{mm}(a), т.е. поpядкy a по модyлю mm.

Применительно к нашей задаче это означает, что m должно содержать минимум три попарно взаимно простых сомножителя, значения функции Эйлера от которых должны делится на 3, 5 и 7 соответственно (чтобы после уможения на разные b получились три соответствующих порядка у одного и того же a по возникающим модулям mm).

Наименьшими такими сомножителями будут числа 7, 11 и 29.
Подобрав a, сравноме с элементами порядков 3, 5 и 7 по этим модулям, получим на множестве классов вычетов по модулю m₀ = 7*11*29 унар, содержащий циклы длины 3, 5 и 7.

Однако m₀ не годится в качестве m. В самом деле, ф(7)/3 = 2, ф(11)/5 = 2 и ф(29)/7 = 4. Потому при подходящем a будут возникать всего 2 цикла длины 3, 2 цикла длины 5 и 4 цикла длины 7. (ф(n) - функция Эйлера).

Увеличивать количество циклов данных длин можно разными путями:

1. Заменить числа 7, 11 и 29 на бОльшие простые таким образом, чтобы значения функции Эйлера этих чисел по-прежнему делились на 3, 5 и 7 соответственно. Этот способ не слишком экономичен. В самом деле, замена 7 на 13 увеличить до 4 количество циклов длины 3, но не добавит циклов длин 5 и 7.
Поэтому наименьшим подходящим m, полученным таким способом будет m = 13*31*71 = 28613. При a, равном, например, 250, в соответствующем унаре будет ф(13)/3 = 4 циклов длины 3, ф(31)/5 = 6 циклов длины 5 и ф(71)/7 = 10 циклов длины 7.

2. Домножить найденное m₀, на некоторый множитель. В этом случае необходимо позаботиться о том, чтобы порядок числа a по модулую этого множителя был равен 1 (чтобы не изменились длины циклов, а лишь возросло их количество).
Наименьшим подходящим множителем будет число 3, поскольку 2*ф(11)/5 = 4 и циклов длины 5 будет все еще недостаточно.
Такой подход даст m = 3*7*11*29 = 6699. При a = 16 в соответствующем унаре будет 3*ф(7)/3 = 6 циклов длины 3, 3*ф(11)/5 = 6 циклов длины 5 и 3*ф(29)/7 = 12 циклов длины 7.

3. Заменить числа 7, 11, 29 (или некоторые из них) на 9, 25, 49, значения функции Эйлера которых, тоже кратны 3, 5 и 7 соответственно.
Поскольку ф(9) = 6 = 2*3 так же как и ф(7), этот подход не увеличит количества циклов длины 3 при замене m = 7*11*29 на m = 9*11*29.
Зато замена 7 на 9 позволяет утроить количество циклов длин 5 и 7. Ведь теперь Пятакову достаточно в качестве начальных выбирать числа кратные 29 и 3 (а не 9), поэтому его m'' будет равно 11*3.
Точно так же, при начальных числах кратных 11 и 3, m'' Семака будет равно 29*3.
Аналогичным образом замена в m₀ множителя 11 на 25 позволить упятерить количество циклов длин 3 и 7, а замена 29 на 49 увеличить в 7 раз число циклов длин 3 и 5.

Этот подход позволяет получить сразу несколько m, меньших 3*7*11*29 и удовлетворяющих условиям задачи:

m = 9*25*29 = 6525. В качестве a вновь подходит число 16. А в соотвествующем унаре будет 5*ф(9)/3 = 10 циклов длины 3, 3*ф(20)/5 = 12 циклов длины 5 и 3*5*ф(29)/7 = 60 циклов длины 7;

m = 9*11*49 = 4851. В качестве a можно взять число 169. А в соотвествующем унаре будет 7*ф(9)/3 = 14 циклов длины 3, 7*3*ф(11)/5 = 42 цикла длины 5 и 3*ф(49)/7 = 18 циклов длины 7.

4. Скомбинироать предыдущие способы.
Наименьшим m, полученным таким путем будет m = 2*9*11*29 = 5742. В качестве a можно взять число 25. А в соотвествующем унаре будет 2*ф(9)/3 = 4 цикла длины 3, 2*3*ф(11)/5 =12 циклов длины 5 и 2*3*ф(29)/7 = 24 цикла длины 7;
Однако это значение m больше предыдущего.

Ответ: m = 4851.

Обсуждение

Оба конкурсанта, приславших свои решения этой задачи, не нашли наименьшего подходящего m. Не смог сделать этого и ведущий Марафона, предложивший задачу. Я ошибочно считал наименьшим m = 6699. Этот же вариант ответа был и у Владислава Франка. И лишь после подведения итогов шестого тура Марафона, в который входила задача № 60, Барух Зив указал мне на мою оплошность.

Приведенное решение не отталкивается напрямую от системы сравнений
{x*a^3 == x (mod m), y*a^5 == y (mod m), z*a^7 == z (mod m)},
продиктованной ситуацией именно этой задачи, а претендует на некоторую универсальность.
Его очевидным образом можно приспособить для моделирования любых конечных унаров, в том числе, содержащих "хвосты" любой "длины" и "ветвистости".
Например, глубина (расстояние до цикла) элемента b в принятых ранее обозначениях определяется как минимум целых неотрицательных h таких, что b_i + h*a_i >= m_i для всех i.

Награды

За решение этой задачи Владислав Франк получает 12 призовых баллов. Виктор Филимоненков (найденное им m - существенно больше) получает 10 баллов.

Эстетическая оценка задачи - 4 балла