Число решений сравнения

[Ward]

Здравствуйте!

Доказать, что число решений сравнения $x^2\equiv 1 \pmod {2^{\alpha}}$ при $\alpha\geqslant 3$ имеет $4$ решения.

Я вроде сделал так:
Понятно что $1$ будет решением. Кроме того, $-1$ будет решением, причем они принадлежат разным классам.
Также решением будет $2^{\alpha-1}-1$. По той же причине решением еще будет $-(2^{\alpha-1}-1).
Получаем всего 4 решения. Вроде так решил.

Можно ли еще как-то по-другому?

[nnosipov]

Ward в сообщении #781801 писал(а):

Получаем всего 4 решения. Вроде так решил.

А вдруг есть какое-то 5-е решение? Из Ваших рассуждений как-то не вытекает, что его нет. Здесь нужны ещё некоторые заклинания.

[Ward]

nnosipov
Да Вы правы.
А как тогда показать, что других решений больше нет?

[provincialka]

А по простому. Через делимость, например. И лучше переписать равенство в виде
$x^2-1\equiv 0 \pmod {2^{\alpha}}$

[Ward]

Ну да.
Получаем, что $(x-1)(x+1)\equiv 0 \pmod {2^{\alpha}}$ Возможны 2 случая:
1) $x-1\equiv 0 \pmod {2}$ и $x+1\equiv 0 \pmod {2^{\alpha-1}}$
2) $x+1\equiv 0 \pmod {2}$ и $x-1\equiv 0 \pmod {2^{\alpha-1}}$
А вот дальше что-то не соображу

[nnosipov]

В этих двух случаях всё будет хорошо, нужно только ещё объяснить, что никакого 3-го случая нет. Хотя это практически очевидно, но объяснить нужно.

[Ward]

nnosipov
Объяснить это смогу.
А как решить скажем пункт 1) ?
не могу понять.

[nnosipov]

Ward в сообщении #781824 писал(а):

А как решить скажем пункт 1) ?

Из сравнения $x-1 \equiv 0 \pmod{2}$ следует, что $x=2k-1$. Подставим это в сравнение $x+1 \equiv 0 \pmod{2^{\alpha-1}}$ и посмотрим.

[Ward]

nnosipov
Ну да получаем, что $k \equiv 0 \pmod{2^{\alpha-2}}$

[provincialka]

Или так. Если один из сомножителей четный, то и другой четный. Но на 4 может делится только один. Значит, один сомножитель делится на 2 только в первой степени, а другой - на $2^{\alpha-1}$

[Ward]

Я вот не знаю как решить пункт 1)
Получаем, что $k\equiv 0 \pmod {2^{\alpha-2}}$.
А что отсюда следует?

[nnosipov]

Ну как что? Раз $k \equiv 0 \pmod{2^{\alpha-2}}$, значит $k=2^{\alpha-2}l$, а тогда $x=2k-1=2^{\alpha-1}l-1$. И Вы получаете либо $x \equiv 2^{\alpha-1}-1 \pmod{2^\alpha}$ (при нечётном $l$), либо $x \equiv -1 \pmod{2^\alpha}$ (при чётном $l$).

[Ward]

nnosipov
Большое Вам спасибо!
Теперь понял!