Помогите решить сравнение

[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. Мож есть у кого мысли, как прийти к такому ответу?

[Бодигрим]

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

[berant]

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

[bot]

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$.

[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$.

[bot]

Не, по этой формуле для $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$.
Хм, а дальше?

[RIP]

bot писал(а):

Хм, а дальше?

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

[maxal]

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}.$

[bot]

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}.$

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

[RIP]

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

[bot]

Задурился экономией - взял своё описание по модулю $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 часа консультации, но не получилось. Снова писать то же самое уже рука не поднимается.