система сравнений по модулю P^2

[vasili]

Помогите доказать!


Система сравнений по модулю $P^2$»


Пусть P - простое число $> 3$ и система сравнений по модулю $P^2$ (далее система сравнений)

$r_1^P - r_1^Pr_3^P\equiv 1\mod P^2$,

$r_2^P - r_2^Pr_1^P\equiv 1\mod P^2$,

$r_3^P - r_3^Pr_2^P\equiv 1\mod P^2$, где

($r_1$, $r_2$ и $r_3$) - наименьшие натуральные вычеты, приведенной системы вычетов,

по модулю $P^2$.


Прошу помощи в доказательстве того, что указанная система сравнений не имеет решений,

если P = 6n +5 и имеет решения для P = 6n + 1 только, если

$r_1^6^n^+^1\equiv r_2^6^n^+^1\equiv r_3^6^n^+^1\mod (6n + 1)^2$.


Предлагаю нижеследующее доказательство

Рассмотрим множество вычетов вида {$R\equiv g^m^P\mod P^2$},

(далее множество вычетов {R}), где

g – наименьший первообразный корень по модулю $P ^2$, а

m пробегает наименьшие натуральные вычеты $m =1,2,3, \cdots ,(P -1)$ по модулю P.

Очевидно вычеты чисел $r_1^P$, $r_2^P$ и $r_3^P$ принадлежат множеству {R}.

Мною рассмотрены множества вычетов {R} по следующим модулям:

$5^2$, $7^2$, $11^2$, $13^2$, $17^2$, $19^2$ и $31^2$, что позволило

высказать нижеследующие Утверждения:

Утверждение 1.

Пусть простое число $P = 6n + 1$, тогда в множестве вычетов {R},

имеются только два вычета:

$R_1\equiv g^n^P\mod P^2$ и .

$R_2\equiv g^5^n^P$, таких, что

$R_1 + R_2\equiv 1\mod P^2\engo (1)$.


Утверждение 2.

Пусть простое число $P = 6n + 5$, тогда в множестве вычетов {R},

нет ни одной пары вычетов, удовлетворяющих условию (1).

Доказательство Утверждения 1

Покажем, что сравнение (1) справедливо.

Пусть функция Эйлера $\varphi (6n + 1)^2 = 6n(6n +1) = 6nP$.

Обозначим вычеты множества {R}, индексы которых кратны $nP$.

Пусть

$R_1\equiv g^n^P\mod P^2$,

$U_1\equiv g^2^n^P\mod P^2$,

$-1\equiv g^3^n^P\mod P^2$,

$U_2\equiv g^4^n^P\mod P^2$,

$R_2\equiv g^5^n^P\mod P^2$,

$1\equiv g^6^n^P\mod P^2$.


Очевидно, вычеты $R_1$ и $R_2$ принадлежат показателю 6 по модулю $P^2$ и

вычетов, принадлежащих показателю 6 по указанному модулю, только 2(два), так как

$\varphi(6)\ = 2$, а потому


$(R_1)^3\equiv -1\mod P^2$, отсюда

$(R_1 + 1)(R_1^2 -R_1 + 1)\equiv 0\mod P^2$, а значит

$R_1^2 -R_1 + 1\equiv 0\mod P^2$, тогда

$R_1 + (-1)R_1^2\equiv 1\mod P^2$ или

$g ^ n ^P + g^3^n^P g^2^n^P\equiv g ^ n ^P + g^5^n^P\equiv R_1 + R_2\equiv1\mod P^2$, что

соответствует сравнению (1).

Обратим внимание на симметричность индексов вычетов $R_1$ и $R_2$ относительно индекса вычета $-1$ равного $3nP$, так

$Ihd R_1 = 3nP-2nP = nP$, а

$Ihd R_2 = 3nP + 2nP = 5nP$.

Пусть существуют в множестве вычетов {R} вычеты $R_3$ и $R_4$, удовлетворяющие условию (1), т.е.

$R_3 + R_4\equiv1\mod P^2$

и пусть

$R_3\equiv g^3^n^P^-^m^1^P$,

$R_4\equiv g^3^n^P^+^m^1^P$, где $m_1< 3n$, но больше или равно 1,

$g^3^n^P^-^m^1^P + g^3^n^P^+^m^1^P\equiv 1\mod P^2$.

Умножим последнее сравнение на $g^m^1^P$ и, учитывая что $(-1)\equiv g^3^n^P\mod P^2$

имеем

$(g^m^1^P)^2 + g^m^1^P + 1\equiv 0\mod P^2$, тогда

$(g^m^1^P)^3\equiv 1\mod P^2$, отсюда

$3m_1P\equiv 0\mod 6nP$, отсюда

$m_1 = 2n$
или
$m_1 = 4n$, тогда

$R_3\equiv g^3^n^P^-^2^n^P\equiv g^n^P\equiv R_1\mod P^2$

или

$R_3\equiv g^3^n^P^-^4^n^P\equiv g^-^n^P\equiv g^6^n^P^-^n^P\equiv g^5^n^P\equiv R_2\mod P^2$.

Пришли к противоречию: вычет $R_3$ равен вычету $R_1$ или вычету $R_2$, что

указывает на справедливость Утверждения 1.

Доказательство Утверждения 2

Функция Эйлера $\varphi (6n + 5)^2 = (6n +4)(6n + 5)$ не делиться на 3 и 6, а потому не существует вычетов в множестве вычетов {R} принадлежащих числам 3 и 6, а значит нет вычетов удовлетворяющих условию (1).

Я проверил частные множества вычетов {R} по модулям $5^2$, $11^2$ и $17^2$
Утверждение 2 везде подтверждалось.


Если Утверждение 1 верно, то тогда из системы сравнений

$r_1^P + (-1) r_1^Pr_3^P\equiv 1\mod P^2$,

$r_2^P + (-1) r_2^Pr_1^P\equiv1\mod P^2$,

$r_3^P + (-1) r_3^Pr_2^P\equiv 1\mod P^2$,

следует, что только одно из них справедливо, т.е. соответствует сравнению (1).

Для определенности пусть справедливо верхнее сравнение, т.е.

$r_1^P\equiv R_1\equiv g^n^P\mod P^2$,

$(-1) r_1^Pr_3\equiv R_2\equiv g^5^n^P\mod P^2$, отсюда с учетом

$(-1)\equiv g^3^n^P\mod P^2$, имеем

$r_3^P\equiv g^5^n^P^-^4^n^P\equiv g^n^P\equiv R_1\mod P^2$, тогда

$r_1^P\equiv r_3^P\mod P^2$, а

из нижнего сравнения

$r_3^P + (-1) r_3^Pr_2^P\equiv1\modP^2$, имеем

$R_1 + (-1) R_1 r_2^P\equiv 1\mod P^2\engo (a) $, но благодаря (1)

$R_1 + R_2\equiv 1\mod P^2$, из сравнений (а) и (1) следует, что

$R_2\equiv (-1)R_1r_2^P\mod P^2$, тогда

$g^5^n^P\equiv g^3^n^Pg^n^Pr_2^P\mod P^2$, отсюда

$r_2^P\equiv g^n^P\equiv R_1\mod P^2$, таким образом, получили

$r_1^P\equiv r_2^P\equiv r_3^P\equiv R_1\mod P^2$..

Аналогичные результаты получим, если для определенности примем

$r_1^P\equiv R_2\equiv g^5^n^P\mod P^2$, тогда будет

$r_1^P\equiv r_2^P\equiv r_3^P\equiv R_2\mod P^2$.

Оба результата есть то, что и требовалось доказать.

Если верно Утверждение 2, то ни одно из сравнений, принадлежащее указанной системе сравнений, не справедливо.

Однако я не уверен, что предложенные мною доказательства Утверждений 1 и 2 являются достаточными, а потому прошу помощи.

[nnosipov]

vasili в сообщении #770276 писал(а):

Прошу помощи в доказательстве того, что указанная система сравнений не имеет решений, если P = 6n +5

Это неверно: первый контрпример при $P=59$, а именно, $r_1=4$, $r_2=39$, $r_3=45$.

-- Чт окт 03, 2013 21:52:52 --

vasili в сообщении #770276 писал(а):

и имеет решения для P = 6n + 1

А вот это верное утверждение: достаточно взять $r_1=a$, $r_2=(1-a)^{-1} \bmod{P^2}$, $r_3=(a-1)a^{-1} \bmod{P^2}$, где $a$ удовлетворяет сравнению $a^P+(1-a)^P \equiv 1 \pmod{P^2}$ и ограничениям $a \not\equiv 0 \pmod{P}$, $a \not\equiv 1 \pmod{P}$. Такое $a$ всегда найдётся, поскольку при $P=6n+1$ многочлен $a^P+(1-a)^P-1$ делится на $a^2-a+1$ и сравнение $a^2-a+1 \equiv 0 \pmod{P^2}$ разрешимо (ибо разрешимо сравнение $a^2-a+1 \equiv 0 \pmod{P}$).