2014 dxdy logo

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

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




 
 Помогите решить сравнение
Сообщение02.06.2008, 14:15 
Решить сравнение: $2^n\equiv n^2\pmod p$ , где р - простое число. Есть подсказка (в задачнике): положить $n=a+(p-1)b$; и даже ответ есть: $ n\equiv pa-(p-1)2^a\pmod p(p-1)$, а=0,1,...,p-2. Мож есть у кого мысли, как прийти к такому ответу?

 
 
 
 
Сообщение02.06.2008, 14:57 
Аватара пользователя
Выражение $n\equiv pa-(p-1)2^a \pmod{p(p-1)}$ получается при решении системы сравнений $n\equiv 2^a \pmod p$ и $n\equiv a \pmod{p-1}$. Первое сравнение - результат применения малой теоремы Ферма, второе - предложенной замены.

 
 
 
 
Сообщение02.06.2008, 19:24 
Вот только я не пойму, как получить $n\equiv 2^a\pmod p$ из $n^2\equiv 2^a\pmod p$.

 
 
 
 Re: Помогите решить сравнение
Сообщение03.06.2008, 07:08 
Аватара пользователя
berant писал(а):
Решить сравнение: $2^n\equiv n^2\pmod p$ , где р - простое число. Есть подсказка (в задачнике): положить $n=a+(p-1)b$; и даже ответ есть: $ n\equiv pa-(p-1)2^a \pmod {p(p-1)}$, а=0,1,...,p-2. Мож есть у кого мысли, как прийти к такому ответу?

Я так полагаю, что Бодигрим не заметил квадрата. Подсказка и ответ к другой задаче $2^n\equiv n \pmod p$.

Здесь можно действовать аналогично, но ответ запишется в неявной форме:

$x\equiv a \pmod {p-1}, \ \ (a-b)^2 \equiv 2^a \pmod p$

При чётных $a$ из второго сравнения очевидным образом находим $b$ и получаем явную серию, а в случаях $p=8k\pm 1$ второе сравнение разрешимо и при нечётных $a$, поэтому появится ещё дополнительная серия, которую тоже можно записать явно если знать решение сравнения $x^2 \equiv 2 \pmod p$.

 
 
 
 
Сообщение06.06.2008, 17:26 
Аватара пользователя
Для простого $p>2$ можно записать и в явной параметрической форме:

$$n\equiv 2pk - (p-1)2^k \pmod{p\cdot\mathbin{\rm ord}_p 2},$$

где $k$ пробегает числа $1, 2, \dots, \mathbin{\rm ord}_p 2$ и $\mathbin{\rm ord}_p 2$ - мультипликативный порядок (показатель) $2$ по модулю $p$.

 
 
 
 
Сообщение07.06.2008, 04:29 
Аватара пользователя
Не, по этой формуле для $p=7$ получаются $n\equiv 2, \ 4, \ 15 \pmod {21}$ и не хватает $n\equiv 5, \ 6, \ 10 \pmod {21}$

Если не задуряться экономией за счёт того, что 2 не всегда примитивен по модулю p, то описание по модулю p(p-1) получается такое:

Явная серия для любого p>2:

$n\equiv 2kp\pm (p-1)2^k, \ k=0, 1, ... \frac{p-3}{2} \pmod {p^2-p}$

Дополнительная неявная серия для $p\equiv \pm 1 \pmod 8$:

$n\equiv (2k+1)p\pm (p-1)\sqrt 2\cdot2^k, \ k=0, 1, ... \frac{p-3}{2} \pmod {p^2-p}$

Здесь $\sqrt 2$ - решение сравнения $x^2\pmod p$, в этом и неявность серии.

Добавлено спустя 22 минуты 26 секунд:

Хотя стоп, если в Вашей формуле заменить минус на $\pm$, то сходится по крайней мере для 7-ки.

$$n\equiv 2pk \pm (p-1)2^k \pmod{p\cdot\mathbin{\rm ord}_p 2},$$

Похоже сойдётся для случая, когда $2 \cdot\mathbin{\rm ord}_p 2=p-1$.
Хм, а дальше?

 
 
 
 
Сообщение07.06.2008, 06:04 
Аватара пользователя
bot писал(а):
Хм, а дальше?

Попробуйте потестить $p=17$.

 
 
 
 
Сообщение07.06.2008, 09:29 
Аватара пользователя
maxal писал(а):
Для простого $p>2$ можно записать и в явной параметрической форме:

$$n\equiv 2pk - (p-1)2^k \pmod{p\cdot\mathbin{\rm ord}_p 2},$$

где $k$ пробегает числа $1, 2, \dots, \mathbin{\rm ord}_p 2$ и $\mathbin{\rm ord}_p 2$ - мультипликативный порядок (показатель) $2$ по модулю $p$.

Это решение на самом деле только для случая $\left(\frac{2}{p}\right)=-1$ (то есть, $p\equiv 3$ или $5\pmod8$).
Для случае $\left(\frac{2}{p}\right)=1$ (то есть $p\equiv \pm 1\pmod8$) решение будет таким:
$$n\equiv pk - (p-1)z^k \pmod{p\cdot\mathbin{\rm ord}_p 2},$$
где $k$ пробегает числа $1, 2, \dots, 2\mathbin{\rm ord}_p 2$, а число $z$ - это корень из 2 (любой), то есть удовлетворяет сравнению: $z^2\equiv 2\pmod{p}.$

 
 
 
 
Сообщение07.06.2008, 10:06 
Аватара пользователя
RIP писал(а):
bot писал(а):
Хм, а дальше?

Попробуйте потестить $p=17$.

Ага, пока студенты готовились, делать было нечего, его и взял - не сошлось, чему не удивился.

Добавлено спустя 8 минут 29 секунд:

maxal писал(а):
Для случае $\left(\frac{2}{p}\right)=1$ (то есть $p\equiv \pm 1\pmod8$) решение будет таким:
$$n\equiv pk - (p-1)z^k \pmod{p\cdot\mathbin{\rm ord}_p 2},$$
где $k$ пробегает числа $1, 2, \dots, 2\mathbin{\rm ord}_p 2$, а число $z$ - это корень из 2 (любой), то есть удовлетворяет сравнению: $z^2\equiv 2\pmod{p}.$

Похоже так, но я не задурялся с экономией, но всё же это неявная серия - корень из двойки знать надо. Явной формулы я не знаю.

 
 
 
 
Сообщение07.06.2008, 20:17 
Аватара пользователя
Первая формула maxal (с поправкой $\pm$) годится и для $p\equiv-1\pmod8$. И вообще, она будет давать не все решения для тех (и только тех) простых $p\equiv1\pmod8$, для которых $\mathop{\mathrm{ord}}_p2\equiv0\pmod2$.

 
 
 
 
Сообщение09.06.2008, 13:28 
Аватара пользователя
Задурился экономией - взял своё описание по модулю $p(p-1)$, расписал его по модулям $p$ и $ord_p2$, а потом снова собрал по китайской теореме об остатках. В итоге получилось:

$$n\equiv kp\pm 2^{\frac{k}{2}}(p-1), \ \ k=0,1, ... , ord_p2 -1$$

Здесь подразумевается, что для $p\equiv \pm 3 \pmod 8$ следует брать только чётные $k$, а для $p\equiv \pm 1 \pmod 8$ под возникающим $\sqrt 2$ при нечётных $k$ надо понимать одно из двух решений сравнения $z^2\equiv 2 \pmod p$.
То есть фактически в написанном выше описании по модулю $p(p-1)$ этот модуль можно уменьшить до указанного maxalом $p\cdot ord_p2$.

P.S. Не сразу заметил, что у Maxalа только половина решений, в связи с чем побредил здесь немножко, пытаясь с помощью перенумерации избавиться от плюса или минуса.
P.P.S. Спохватился, что может быть зря удалил бред, Хотел было его восстановить путём возврата, чтобы показать до какой степени отупения можно дойти за каких-нибудь 3 часа консультации, но не получилось. Снова писать то же самое уже рука не поднимается. :D

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


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