Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

Предыдущая версия справа и слева Предыдущая версия
Следующая версия Следующая версия справа и слева
ent2 [2015/09/21 23:01]
Уланский Евгений Алесандрович [Лемма Гензеля] 		ent2 [2015/09/21 23:19]
Уланский Евгений Алесандрович [Лемма Гензеля]
Строка 270: Строка 270:
 Если сравнение $x^2\equiv A\pmod{p}$ неразрешимо,​ то и наше сравнение не может иметь решений при любом натуральном $k$. Если сравнение $x^2\equiv A\pmod{p}$ имеет единственное решение,​ то $A\equiv 0\pmod{p}$, а значит и решением будет $x_1\equiv 0\pmod{p}$. В этом случае лемма Гензеля неприменима,​ так как при $f(x)=x^2$ будем иметь $f'​(x)=2x$,​ но $2x_1\equiv 0\pmod{p}$. Однако этот случай достаточно прост, чтобы уделять ему внимание. Пусть теперь сравнение $x^2\equiv A\pmod{p}$ имеет два различных решения $x\equiv\pm x_1\pmod{p}$. Из того, что они различны,​ следует $2x_1\not\equiv 0\pmod{p}$ и лемма Гензеля может быть применена. Из неё следует,​ что для каждого натурального $k$ будет иметься ровно два различных решения сравнения $x^2\equiv A\pmod{p^k}$. Если сравнение $x^2\equiv A\pmod{p}$ неразрешимо,​ то и наше сравнение не может иметь решений при любом натуральном $k$. Если сравнение $x^2\equiv A\pmod{p}$ имеет единственное решение,​ то $A\equiv 0\pmod{p}$, а значит и решением будет $x_1\equiv 0\pmod{p}$. В этом случае лемма Гензеля неприменима,​ так как при $f(x)=x^2$ будем иметь $f'​(x)=2x$,​ но $2x_1\equiv 0\pmod{p}$. Однако этот случай достаточно прост, чтобы уделять ему внимание. Пусть теперь сравнение $x^2\equiv A\pmod{p}$ имеет два различных решения $x\equiv\pm x_1\pmod{p}$. Из того, что они различны,​ следует $2x_1\not\equiv 0\pmod{p}$ и лемма Гензеля может быть применена. Из неё следует,​ что для каждого натурального $k$ будет иметься ровно два различных решения сравнения $x^2\equiv A\pmod{p^k}$.
  
-Из всего вышесказанного видно, что для нечётного числа $P=p_1^{k_1}\cdots ​p_s^{k_s}$ //​**сравнение**//​ $x^2\equiv A\pmod{P}$ //​**при**//​ $(A,P)=1$ //​**будет разрешимо тогда и только тогда, когда разрешимо каждое из сравнений**//​ $x^2\equiv A\pmod{p_i},​\ i=1,\ldots ,s$.+Из всего вышесказанного видно, что для нечётного числа $P=p_1^{k_1}\cdots ​p_m^{k_m}$ //​**сравнение**//​ $x^2\equiv A\pmod{P}$ //​**при**//​ $(A,P)=1$ //​**будет разрешимо тогда и только тогда, когда разрешимо каждое из сравнений**//​ $x^2\equiv A\pmod{p_i},​\ i=1,\ldots ,s$, так как отсутствие решений хотя бы по одному простому модулю гарантирует отсутствие решений и по модулю $P$, а наличие решений по каждому из простых модулей по Лемме Гензеля даёт также решения и по модулю степеней этих простых чисел: $x\equiv x_1\pmod{p_1^{k_1}},​\ldots ,x\equiv x_m\pmod{p_m^{k_m}}$. Решая полученную систему сравнений (с помощью китайской теоремы об остатках),​ мы получим решение исходного сравнения по модулю $P$. Всего таких решений найдётся $2^m$, так как по каждому из модулей $p_1^{k_1},​\ldots ,p_m^{k_m}$ будет два решения.
    
-Для полноты картины изучим случай $p=2$. По модулям $2$ и $4$ ситуация прозрачна.+Для полноты картины изучим случай $p=2$, при котором лемма Гензеля для сравнения $x^2\equiv A\pmod{2^k}$ также неприменима,​ поскольку $2x_1\equiv 0\pmod{2}$ независимо от значения $x_1$. По модулям $2$ и $4$ ситуация прозрачна.
  
-**Предложение 4**. Пусть $a\in\mathbb{Z}$ нечётно,​ $k\in\mathbb{N},​\ k\geqslant 3$. Тогда сравнение $x^2\equiv ​a\pmod{2^k}$ имеет $4$ решения,​ если $a\equiv 1\pmod{8}$, и неразрешимо иначе.+**Предложение 4**. Пусть $A\in\mathbb{Z}$ нечётно,​ $k\in\mathbb{N},​\ k\geqslant 3$. Тогда сравнение $x^2\equiv ​A\pmod{2^k}$ имеет $4$ решения,​ если $A\equiv 1\pmod{8}$, и неразрешимо иначе.
  
-**Доказательство**. Проведём индукцию по $k$. При $k=3$ четыре числа $\pm 1,\pm 3$ удовлетворяют сравнению $x^2\equiv 1\pmod{8}$, а так как они образуют приведённую систему вычетов по модулю $8$, то это все решения данного сравнения. Из этого же следует,​ что сравнения $x^2\equiv ​a\pmod{8}$ неразрешимы при $a=-1,\pm 3$.+**Доказательство**. Проведём индукцию по $k$. При $k=3$ четыре числа $\pm 1,\pm 3$ удовлетворяют сравнению $x^2\equiv 1\pmod{8}$, а так как они образуют приведённую систему вычетов по модулю $8$, то это все решения данного сравнения. Из этого же следует,​ что сравнения $x^2\equiv ​A\pmod{8}$ неразрешимы при $A=-1,\pm 3$.
  
-Пусть теперь для некоторого $k\geqslant 3$ предложение верно. Выберем некоторое $a\equiv 1\pmod{8}$. По предположению индукции найдётся некоторое нечётное число $x_k$ такое, что $x_k^2\equiv ​a\pmod{2^k}$,​ то есть $x_k^2=a+c\cdot 2^k$. Если теперь $c$ чётно, то $x_k^2\equiv ​a\pmod{2^{k+1}}$. Если же $c$ нечётно,​ то $(x_k+2^{k-1})^2\equiv ​a\pmod{2^{k+1}}$,​ то есть сравнение $x^2\equiv ​a\pmod{2^{k+1}}$ будет иметь некоторое решение $x_{k+1}$. Но вместе с ним оно будет иметь по крайней мере четыре решения $\pm x_{k+1}\pm 2^k$. C другой стороны,​ поскольку в приведённой системе вычетов по модулю $2^{k+1}$ ровно каждое четвёртое число сравнимо с $1$ по модулю $8$, то, взяв для каждого из этих чисел по четыре решения соответствующего сравнения,​ мы уже исчерпаем всю приведённую систему вычетов по модулю $2^{k+1}$, а значит более четырёх решений ни у одного из этих сравнений быть не может. Более того, не может быть решений и у сравнений $x^2\equiv ​a\pmod{2^{k+1}}$ при $a\not\equiv 1\pmod{8}$. **Предложение 4 доказано**.+Пусть теперь для некоторого $k\geqslant 3$ предложение верно. Выберем некоторое $A\equiv 1\pmod{8}$. По предположению индукции найдётся некоторое нечётное число $x_k$ такое, что $x_k^2\equiv ​A\pmod{2^k}$,​ то есть $x_k^2=A+c\cdot 2^k$. Если теперь $c$ чётно, то $x_k^2\equiv ​A\pmod{2^{k+1}}$. Если же $c$ нечётно,​ то $(x_k+2^{k-1})^2\equiv ​A\pmod{2^{k+1}}$,​ то есть сравнение $x^2\equiv ​A\pmod{2^{k+1}}$ будет иметь некоторое решение $x_{k+1}$. Но вместе с ним оно будет иметь по крайней мере четыре решения $\pm x_{k+1}\pm 2^k$. C другой стороны,​ поскольку в приведённой системе вычетов по модулю $2^{k+1}$ ровно каждое четвёртое число сравнимо с $1$ по модулю $8$, то, взяв для каждого из этих чисел по четыре решения соответствующего сравнения,​ мы уже исчерпаем всю приведённую систему вычетов по модулю $2^{k+1}$, а значит более четырёх решений ни у одного из этих сравнений быть не может. Более того, не может быть решений и у сравнений $x^2\equiv ​A\pmod{2^{k+1}}$ при $A\not\equiv 1\pmod{8}$. **Предложение 4 доказано**.