2014 dxdy logo

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

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




 
 Число решений сравнения
Сообщение29.10.2013, 16:07 
Здравствуйте!

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

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

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

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:15 
Ward в сообщении #781801 писал(а):
Получаем всего 4 решения. Вроде так решил.
А вдруг есть какое-то 5-е решение? Из Ваших рассуждений как-то не вытекает, что его нет. Здесь нужны ещё некоторые заклинания.

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:20 
nnosipov
Да Вы правы.
А как тогда показать, что других решений больше нет?

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:25 
Аватара пользователя
А по простому. Через делимость, например. И лучше переписать равенство в виде
$x^2-1\equiv 0 \pmod {2^{\alpha}}$

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:29 
Ну да.
Получаем, что $(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}}$
А вот дальше что-то не соображу

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

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:34 
nnosipov
Объяснить это смогу.
А как решить скажем пункт 1) ?
не могу понять.

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:47 
Ward в сообщении #781824 писал(а):
А как решить скажем пункт 1) ?
Из сравнения $x-1 \equiv 0 \pmod{2}$ следует, что $x=2k-1$. Подставим это в сравнение $x+1 \equiv 0 \pmod{2^{\alpha-1}}$ и посмотрим.

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:52 
nnosipov
Ну да получаем, что $k \equiv 0 \pmod{2^{\alpha-2}}$

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 16:54 
Аватара пользователя
Или так. Если один из сомножителей четный, то и другой четный. Но на 4 может делится только один. Значит, один сомножитель делится на 2 только в первой степени, а другой - на $2^{\alpha-1}$

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 17:03 
Я вот не знаю как решить пункт 1)
Получаем, что $k\equiv 0 \pmod {2^{\alpha-2}}$.
А что отсюда следует?

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 17:08 
Ну как что? Раз $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$).

 
 
 
 Re: Число решений сравнения
Сообщение29.10.2013, 17:14 
nnosipov
Большое Вам спасибо!
Теперь понял!

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


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