LINUX.ORG.RU
решено Форум — Development  

[задачи][числовая последовательность] Задача о последовательности остатков от деления


0

1

Собственно задача.

Случайно обнаружил, что эта последовательность относится к линейно-конгруэнтному методу. Поиск дал следующие свойства этой последовательности: 

1)НОД(c,m) = 1 (то есть, c и m взаимно просты);
2)a-1 кратно p для всех простых делителей p числа m;
3)a-1 кратно 4, если m кратно 4.
Существуют ли другие свойства этой последовательности? Можно ли как то напрямую вычислить требуемые величины? Где можно прочитать о исследовании таких последовательностей?

P.S.: Я ищу не ответ, а путь к решению, подсказку.

★★★

Последнее исправление: TheKnight (всего исправлений: 2)

Кнут том 2.

anonymous
()
Ответ на: комментарий от Pi

> Конечное поле

Особенно для M=4, да

anonymous
()

Есть мысль о том, как задачу свести к теореме Эйлера.

a1 = X * a0 + Y, a2 = X * (X * a0 + Y) + Y, a3 = ..., an = X^n * a0 + (X^(n-1) + ... + 1) * Y

Соответственно, надо бы найти минимальное n, такое что an = a0 (mod M). Переносим a0 влево и делаем чуток преобразований.

(X^n - 1) * a0 + (X^(n-1) + ... + 1) * Y = (X^(n-1) + ... + 1) * ((X - 1) * a0 + Y) = 0 (mod M) — такое уравнение уже решать проще, ибо можно разделить на Z = НОД(M, (X - 1) * a0 + Y), пусть M' = M / Z. Тогда уравнение сводится к X^(n-1) + ... + 1 = 0 (mod M'). Что можно домножить на X - 1 и получить красоту.

X^n - 1 = 0 (mod M'*(X - 1)), где минимальный n можно найти по теореме Эйлера.

Таким образом для решения задачи требуется применить алгоритм Евклида и посчитать функцию Эйлера (что легко делается, если применить разложение на множители).

anonymous
()
Ответ на: комментарий от anonymous

Хм, тут правда есть некоторая трудность, что теорема Эйлера только для взаимнопростых чисел работает, да и с a0 сравнивать не очень корректно в случае, когда цикл не сразу начинается. В общем, надо бы додумать.

anonymous
()
Ответ на: комментарий от anonymous

О, придумал.

Берем не an = a0 (mod M), но an = ak (mod M). Так же, как и раньше, вычитаем a0 и раскладываем на множители: ((X - 1) * a0 + Y) * (X^(n-1) + ... + 1) = ((X - 1) * a0 + Y) * (X^(k-1) + ... + 1) (mod M); так же, как и раньше, делим на НОД: X^(n-1) + ... + 1 = X^(k-1) + ... + 1 (mod M'); так же, как и раньше, умножаем на X-1: X^n - 1 = X^k - 1 (mod M"), где M" = M' * (X - 1).

Получили уравнение X^n = X^k (mod M"), в котором нужно найти минимальные неравные n и k, далее X^k * (X^(n-k) - 1) = 0 (mod M"). Дальше надо рассматривать разложения на множители X и M". Те множители, которые у них общие, набираются с помощью X^k, а остальные с помощью X^(n-k) - 1. Для первого нужно разложение на простые множители, а для второго теорема Эйлера. Всё.

anonymous
()

Итог - оказывается, для этой последовательности можно воспользовать отображением числа последовательности на его номер в ней. До зацикливания все числа уникальны. Всем спасибо за подсказки.

TheKnight ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development