2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Очередное уравнение в целых числах
Сообщение31.10.2010, 20:04 
$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$ и только их?)
Скажите, можно ли решить это уравнение в общем виде и каким способом? (А дальше я сам. :-) ) Просто интересно…

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение31.10.2010, 20:11 
Дискретное логарифмирование?

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение31.10.2010, 21:28 
А как его производить и над чем?

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

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение31.10.2010, 21:46 
Тут интересно, когда $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}$$
Но оно им всем кратно, конечно.

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

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение31.10.2010, 22:45 
Аватара пользователя
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)$.

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение31.10.2010, 23:25 
Joker_vD в сообщении #368559 писал(а):
В сущности, вы вычисляете порядки элементов кольца $\mathbb Z_b$: $ord(n) \stackrel{def}{=} \min\left\{\, e \in \mathbb N \mid n^e \equiv 1 \pmod{b} \,\right\}$.
Ну да. Только как это может помочь? :-)

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение31.10.2010, 23:59 
arseniiv в сообщении #368605 писал(а):
Ну да. Только как это может помочь?

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

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение01.11.2010, 00:06 
Joker_vD в сообщении #368480 писал(а):
Дискретное логарифмирование?
arseniiv в сообщении #368526 писал(а):
А как его производить и над чем?
Или вы решили, что не поможет? А то в первый раз слышу про такой метод.

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

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

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение01.11.2010, 05:37 
Аватара пользователя
Joker_vD в сообщении #368625 писал(а):
Эффективных алгоритмов нет. Единственно, $ord(n) \mid b - 1$, но это ничего не дает.

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

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение01.11.2010, 20:46 
maxal в сообщении #368671 писал(а):
Имея разложение $b-1$ на простые, порядок $n$ по модулю $b$ легко вычисляется.

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

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение01.11.2010, 21:16 

(Оффтоп)

Joker_vD в сообщении #368647 писал(а):
Слушайте, ну вы хоть википедию открывали?
Простите. Потом открыл и дочитал. :oops:

 
 
 
 Re: Очередное уравнение в целых числах
Сообщение01.11.2010, 22:49 
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)$.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group