Решение сравнения имеет такой вид. Как это доказать?

[farewe11]

Добрый вечер, у меня тут есть задача довольно интересная, только вот плохо то, что не представляется возможным её решить. Есть у нас сравнение $x^2 \equiv a \pmod{p^\alpha}$.
Доказать, что решения этого сравнения имеют такой вид:

$$x\equiv \pm PQ' \pmod{p^\alpha}$$

Где:

$$P = \frac{(z+\sqrt{a})^\alpha+(z-\sqrt{a})}{2}$$

$$Q = \frac{(z+\sqrt{a})^\alpha-(z-\sqrt{a})}{2}$$

$$QQ' \equiv a \pmod{p^\alpha}$$

$$z^2 \equiv a \pmod{p}$$

Как бы удивительно это ни звучало, если бы был известен вид $p^\alpha$, я бы, вероятнее всего, решил бы. Однако сейчас даже не знаю, с чего начать. Издалека, для начала попытавшись узнать вид $Q'$? Что посоветуете?

[Коровьев]

Виноградов. "Основы теории чисел"
Вопросы к главе V. Задача 6 (Один в один )
Книга есть в сети.

[farewe11]

И правда, есть!
Правда, толку немного от этого. Главу, конечно, прочитаю - вдруг что ещё нового узнаю. Но относительно решения вряд ли идеи появятся, уже больше недели думаю над этой задачей.

[farewe11]

..а вот мысли про то, что в конце книги есть решения задач, у меня даже не возникло. Удивительно, каким добросовестным студентом я начинаю становиться
Разбираюсь сейчас в решении. В одном месте застрял. Итак, что нам говорит автор?
1). Очевидно, $P$ и $Q$ целые. (это и правда очевидно)
2). Причем $Q$ по модулю $p$ сравнимо с числом, которое получим, заменяя $a$ на $z^2$, следовательно, заменим $\sqrt{a}$ на $z$. (это тоже более чем очевидно)
Кстати, можно даже увидеть воочию выполнение пункта $2$ на примере. Пусть $\alpha$ - четное, тогда можно представить $Q$ вот так:

$$Q = \frac{(z+\sqrt{a})^\alpha - (z-\sqrt{a})^\alpha}{2\cdot\sqrt{a}} = C_\alpha^1\cdot z^{\alpha-1}\cdot\sqrt{a} + C^3_\alpha\cdot z^{\alpha-3}\cdot\sqrt{a}^3 + \dots + C^{\alpha - 1}_\alpha\cdot z\cdot a^{\frac{\alpha-1}{2}}$$

Так как по условию $z^2\equiv a \pmod {p}$, то справедливость пункта 2 очевидна.
3). Поэтому $Q\equiv 2^{\alpha-1}\cdot z^{\alpha-1} \pmod {p}$.
Почему это? Откуда взялась двойка в степени $\alpha-1$? Что-то непонятно..

-- Чт дек 22, 2011 04:07:43 --

UPD: Разобрался с двойкой, достаточно было лишь в формуле $Q$ из условия заменить $\sqrt{a}$ на $z$... Продвигаемся дальше!
5). Следовательно, $GDC(Q,p) = 1$.
Да, вот этот вывод посложнее будет, за минуту не разобраться...

[Sonic86]

farewe11 в сообщении #518327 писал(а):

5). Следовательно, $GDC(Q,p) = 1$.

следует из

farewe11 в сообщении #518327 писал(а):

3). Поэтому $Q\equiv 2^{\alpha-1}\cdot z^{\alpha-1} \pmod {p}$.

Вообще, интересная задача... Только для решения сравнений таким методом нужно бы еще выписать рекуррентные формулы для $P_{\alpha}, Q_{\alpha}$ (будет просто как для уравнений Пелля).

[nnosipov]

Легко доказывается по индукции (индукция по $\alpha \geqslant 1$).

[farewe11]

Sonic86 в сообщении #518361 писал(а):

farewe11 в сообщении #518327 писал(а):

5). Следовательно, $GDC(Q,p) = 1$.

следует из

farewe11 в сообщении #518327 писал(а):

3). Поэтому $Q\equiv 2^{\alpha-1}\cdot z^{\alpha-1} \pmod {p}$.

Не могу никак что-то логики увидеть. Напомню, что эти утверждения 1)., 2)., 3).. - они не мои, а из книги, я в них сейчас разбираюсь. Почему, если $Q$ сравнимо с $2^{\alpha -1}z^{\alpha-1}$ по модулю $p$, то $Q$ и $p$ - взаимно простые?

[farewe11]

Продолжим разбор решения:

Цитата:

Имеем (1):

$$P^2-aQ^2 = (z+\sqrt{a})^\alpha (z-\sqrt{a})^\alpha = (z^2-a)^\alpha \equiv 0 \pmod{p^\alpha} $$

откуда (2):

$$(PQ')^2 \equiv a(QQ')^2 \equiv a \pmod{p^\alpha} $$

И вот снова загадочное слово "откуда". Почему из первого следует второе? Первое понятно почему справедливо: по условию. Справедливость второго тоже очевидна: $P^2 \equiv aQ^2 \pmod {p^\alpha}$.
Так что вопрос только в следующем: вообще почему автор завел разговор про $P^2-aQ^2$? И почему из (1) следует (2)?

-- Пт дек 23, 2011 06:06:27 --

Напомню, что P и Q имеют такой вид: (в первом сообщении несколько ошибок допустил)

$$P = \frac{(z+\sqrt{a})^\alpha+(z-\sqrt{a})^\alpha}{2}$$

$$Q = \frac{(z+\sqrt{a})^\alpha-(z-\sqrt{a})^\alpha}{2\sqrt{a}}$$

[Sonic86]

farewe11 в сообщении #518714 писал(а):

Почему, если $Q$ сравнимо с $2^{\alpha -1}z^{\alpha-1}$ по модулю $p$, то $Q$ и $p$ - взаимно простые?

Ну очевидно же Ну подставьте $\alpha = 3, z=1, p=5$ например. Рефлексы мозга помогут.

[farewe11]

Sonic86 в сообщении #518782 писал(а):

farewe11 в сообщении #518714 писал(а):

Почему, если $Q$ сравнимо с $2^{\alpha -1}z^{\alpha-1}$ по модулю $p$, то $Q$ и $p$ - взаимно простые?

Ну очевидно же Ну подставьте $\alpha = 3, z=1, p=5$ например. Рефлексы мозга помогут.

Да этот вопрос уже отпал, еще несколько часов назад Рефлексы помогли. Теперь предстоит разобраться со следующим..

[Sonic86]

По-моему, автор просто придерживался логики последовательного изложения, но проще ухватить идею, а детали добавить при необходимости.
Идея такая: если $z^2 \equiv a \pmod p$ - решение для показателя 1, то $(z^2-a)^{\alpha} \equiv 0 \pmod{p^{\alpha}}$ - соотношение, из которого можно построить решение для показателя $\alpha$. Дальше делаем $(z^2-a)^{\alpha}=(z-\sqrt{a})^{\alpha}(z+\sqrt{a})^{\alpha}=|\text{возводим в степень альфа}|=$ $(P-Q\sqrt{a})(P+Q\sqrt{a}) \equiv 0 \pmod{p^{\alpha}} \Leftrightarrow (PQ^{-1})^2 \equiv a \pmod{p^{\alpha}}$. И остается добавить проверку нетривиальности решения, существования обратного и вроде все ($Q'=Q^{-1}$).

upd: т.е. мы решаем как уравнение Пелля:
Пелль в кольце $\mathbb{Z}$: $(x_0 -y_0\sqrt{a})(x_0 +y_0\sqrt{a})=1 \Rightarrow (x_0 -y_0\sqrt{a})^n(x_0 +y_0\sqrt{a})^n=1^n=1$ - получаем все решения (мы этого тут не доказываем, но это так)
Здесь в кольцах $\mathbb{Z}_p^n$: $(z-\sqrt{a})(z-\sqrt{a})=0 \Rightarrow (z-\sqrt{a})^n(z-\sqrt{a})^n=0^n=0$ - тоже получаем все 2 решения для заданного $n$ (доказываем тоже отдельно, но тут это просто).
То же самое! Только вместо 1 у нас 0, и $x_0 \to z, y_0 \to 1$.

[farewe11]

Ну да, то, что Вы описали - вроде понятно.. напоминает метод индукции: сначала для $\alpha=1$, а потом для всех остальных. Спасибо!
Еще, кстати, за доказательство того, что соотношение справедливо для любых $\alpha$, не взялся.. но чувствую, что это будет вовсе не просто. Как это доказать. Маловероятно, что нужно раскрыть скобки и расписать по формуле бинома, и дальше уже внимательнее смотреть.. хотя, такой вариант тоже возможен. Как поступить?

[farewe11]

Да ведь остаток от произведения равен произведению остатков. Поэтому доказательство даже доказывать не надо, всё понятно. :)
Ну а тот факт, что $Q' \equiv Q^{-1}$, следует из условия: $QQ' \equiv 1 \pmod{p^\alpha}$. Достаточно вспомнить словосочетание "мультипликативно обратное число".
Действительно интересная задача.

[Коровьев]

(Оффтоп)

Вот что интересно в этой задаче.
Существование решения $x_0 $ для $\alpha=1$ позволяет получить решение $x_1 $ для $\alpha=2$ и т.д. То есть получить последовательно решения
$\left\{ {x_n} \right\}=\left\{ {x_0},{x_1},...,{x_n},... \right\}$
Так вот, эта последовательность определяет некий новый объект - p-адическое число. И задачка вроде бы рядовая , а подишь ты, привела к созданию мощного мат.инструмента - p-адического анализа.