Очередное уравнение в целых числах

[arseniiv]

$n^{x + 1} \equiv n \mod b$, то есть, $b \backslash n (n^x - 1)$. Интересует наименьший после нуля корень, хотя любое такое число — это количество умножений числа с последней цифрой $n$ в системе счисления с основанием $b$, после которого цифра снова та же. Разумеется, для некоторых $(n;\; b)$, например, $(6;\; 8)$, только один корень — $0$. (И вообще вроде для всех $(n;\; b^n),\; b \backslash n$ и только их?)
Скажите, можно ли решить это уравнение в общем виде и каким способом? (А дальше я сам. ) Просто интересно…

[Joker_vD]

Дискретное логарифмирование?

[arseniiv]

А как его производить и над чем?

[EtCetera]

Вообще-то, если $b$ $\text{---}$ простое, то по МТФ получаем $x\equiv 0\mod p-1$, т.е. наименьшее положительное решение таково: $x=p-1$.

[arseniiv]

Тут интересно, когда $b$ как раз не простое.

-- Пн ноя 01, 2010 01:00:27 --

EtCetera в сообщении #368528 писал(а):

т.е. наименьшее положительное решение таково: $x=p-1$

Кстати, нет. Могут быть и меньше. Посмотрите (обозначим $x = d_b(n)$):

$$\begin{array}{ccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 \\ d_7(n) & 1 & 3 & 6 & 3 & 6 & 2 \\ \end{array}$$

Но оно им всем кратно, конечно.

[Joker_vD]

В сущности, вы вычисляете порядки элементов кольца $\mathbb Z_b$: $ord(n) \stackrel{def}{=} \min\left\{\, e \in \mathbb N \mid n^e \equiv 1 \pmod{b} \,\right\}$.

[age]

arseniiv в сообщении #368474 писал(а):

Скажите, можно ли решить это уравнение в общем виде и каким способом? (А дальше я сам. ) Просто интересно…

Нельзя. Тут три варианта:
$\begin{cases} n\div b\\ n-1\div b\\ \dfrac{n^x-1}{n-1}\div b \end{cases}$
В первых двух случаях никаких ограничений на $b$ нет: если $2\not\|\ n$, то $2\ |\ (n-1)$.

[arseniiv]

Joker_vD в сообщении #368559 писал(а):

В сущности, вы вычисляете порядки элементов кольца $\mathbb Z_b$: $ord(n) \stackrel{def}{=} \min\left\{\, e \in \mathbb N \mid n^e \equiv 1 \pmod{b} \,\right\}$.

Ну да. Только как это может помочь?

[Joker_vD]

arseniiv в сообщении #368605 писал(а):

Ну да. Только как это может помочь?

Ничем. Эффективных алгоритмов нет. Единственно, $ord(n) \mid b - 1$, но это ничего не дает.

[arseniiv]

Joker_vD в сообщении #368480 писал(а):

Дискретное логарифмирование?

arseniiv в сообщении #368526 писал(а):

А как его производить и над чем?

Или вы решили, что не поможет? А то в первый раз слышу про такой метод.

[Joker_vD]

Слушайте, ну вы хоть википедию открывали? Дискретное логарифмирование — нахождение $x$ из уравнения $a^x = b$ в конечной мультипликативной группе. Это не метод, это название операции. Эффективных алгоритмов для совершения такой операции нет. Теоретическое выражение, разумеется, есть:

$a^x \equiv 1 \pmod{p}$ если $x=\sum\limits_{i=1}^{p-2}(1-a^i)^{-1} \mod{p}$ при простом $p$. При составном — раскладывайте на множители и китайская теорема об остатках вам в помощь.

[maxal]

Joker_vD в сообщении #368625 писал(а):

Эффективных алгоритмов нет. Единственно, $ord(n) \mid b - 1$, но это ничего не дает.

Имея разложение $b-1$ на простые, порядок $n$ по модулю $b$ легко вычисляется.

[Joker_vD]

maxal в сообщении #368671 писал(а):

Имея разложение $b-1$ на простые, порядок $n$ по модулю $b$ легко вычисляется.

Вот в том то и проблема, что разложить $b - 1$ на простые множители очень непросто.

[arseniiv]

(Оффтоп)

Joker_vD в сообщении #368647 писал(а):

Слушайте, ну вы хоть википедию открывали?

Простите. Потом открыл и дочитал.

[Ales]

arseniiv в сообщении #368474 писал(а):

$n^{x + 1} \equiv n \mod b$, то есть, $b \backslash n (n^x - 1)$. Интересует наименьший после нуля корень, хотя любое такое число — это количество умножений числа с последней цифрой $n$ в системе счисления с основанием $b$, после которого цифра снова та же. Разумеется, для некоторых $(n;\; b)$, например, $(6;\; 8)$, только один корень — $0$. (И вообще вроде для всех $(n;\; b^n),\; b \backslash n$ и только их?)
Скажите, можно ли решить это уравнение в общем виде и каким способом? (А дальше я сам. ) Просто интересно…

Для решения этого уравнения достаточно знать разложение $b$ на множители.

Достаточность: надо знать малую теорему Ферма, функцию Эйлера, китайскую теорему об остатках.
Необходимо ли знать разложение $b$ на множители? - не знаю.

-- Пн ноя 01, 2010 22:54:44 --

Наименьшее $x$ будет делителем функции Эйлера для числа $b$ - $\phi(b)$.
Значит надо знать разложение на простые $\phi(b)$.