2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 система сравнений по модулю P^2
Сообщение03.10.2013, 15:35 


27/03/12
449
г. новосибирск
Помогите доказать!


Система сравнений по модулю $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 являются достаточными, а потому прошу помощи.

 Профиль  
                  
 
 Re: система сравнений по модулю P^2
Сообщение03.10.2013, 17:02 
Заслуженный участник


20/12/10
8858
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}$).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group