Своиство вычетов по модулю Р^2, индексы которых кратны Р

[vasili]

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


Рассматривая частные примеры наименьших натуральных вычетов по модулю $P^2$,

[ для модулей $P^2 = 5^2, 7^2, 11^2, 13^2. 17^2, 19^2$ и 31^2], индексы, которых

кратные P, (где P - простое нечетное число), я заметил одно свойство таких вычетов,

которое излагаю ниже в Утверждении 1 и в Утверждении 2.

Я пытаюсь найти доказательство этого свойства вычетов, но мои доказательства мне

кажется не полные. А потому прошу помочь мне разобраться в доказательстве этих

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

Пусть {R}- часть приведенной системы наименьших натуральных вычетов по модулю

$P^2$, индексы, которых кратны P, т.е.

$ind R = mP$, где m пробегает наименьшие натуральные вычеты

$m =1,2,3,\cdots\, (P-1)$ по модулю P.


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

Если простое число $P = 6n + 1$, то в системе {R} имеются только 2(два) вычета,

Обозначим их как $R_1$ и $R_2$ таких, что $R_1 + R_2\equiv 1\mod P^2\engo(1)$.



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

Если простое число $P = 6n + 5$, то в системе {R} нет ни одной пары вычетов,

удовлетворяющих условию (1).


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

1. Пусть g –наименьший первообразный корень по модулю $P^2$
и для нашего случая функция Эйлера $\varphi (P^2) = (P-1) P = 6n (6n + 1) = 6nP$


2.Запишем все вычеты системы {R} индексы, которых по модулю $P^2$ кратны

$nP$,

Пусть

$R_1\equiv g^ {nP}\mod P^2$,

$U_1\equiv g^ {2nP}\mod P^2$,

$-1\equiv g^ {3nP}\mod P^2$,

$U_2\equiv g^ {4nP}\mod P^2$,

$R_2\equiv g^ {5nP}\mod P^2$,

$1\equiv g^ {6nP}\mod P^2$.

3.Очевидно в системе {R} имеются вычеты, принадлежащие показателю 6 по модулю,

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



4.Такими вычетами будут вычеты $R_1$ и $R_2$, так как

$ (g^{nP})^6\equiv 1\mod P^2$ и $ (g^{5nP})^6\equiv 1\mod P^2$, а вычеты

$U_1$ и $U_2$ очевидно принадлежат показателю 3 , так как

$(g^{2np})^3\equiv (g^{4nP})^3\equiv 1\mod P^2$,

вычет (-1) явно принадлежит показателю 2.

5.Тогда будут справедливы cравнения:

$ R_1^6-1= (R_1^3-1) (R_1^3 + 1)\equiv 0\mod P^2$,

$R_2^6-1= (R_2^3-1) (R_2^3 + 1)\equiv 0\mod P^2$, отсюда

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

$R_1^2-R_1 +1\equiv 0\mod P^2\engo(2)$,

$R_2^2-R_2 +1\equiv 0\mod P^2engo(3)$,

[ числа $R_1 + 1$ и $R_2 + 1$ не сравнимы с нулем по

модулю $P^2$ , так как в противном случае $R_1\equiv R_2\mod P^2$, что противоречит начальным их значениям.].

6..Вычтем из сравнения (2) сравнение (3)

$R_1^2-R_2^2 -R_1 + R_2 = (R_1-R_2)(R_1 + R_2-1)\equiv 0\mod P^2$, отсюда

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

$R_1 + R_2\equiv 1\mod P^2$, что подтверждает справедливость условия (1).

7.Теперь следует показать, что это единственная пара вычетов $R_1$ , $R_2$, из

системы вычетов {R}, которая удовлетворяет условию (1).

Очевидно, вычеты $U_1$ и $U_2$ не удовлетворяют условию (1), так как

$U_1 + U_2\equiv g^{2nP} + g^{4nP}\equiv g^{2nP} +g^{3nP}g^{nP}\mod P^2$, отсюда

c учетом вычета $-1\equiv g^{3nP}\mod P^2$ имеем

$g^{2nP}-g^{nP}\equiv R_1^2-R_1\mod P^2$, но благодаря (2)

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

$U_1 + U_2\equiv -1\mod P^2$, что и т.д.

8.Пусть существуют вычеты $R_3$ и $R_4$ такие, что

$R_3 + R_4\equiv 1\mod P^2\engo(4)$

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

индекса вычета (-1) равного $3nP$ так:

$ind R_1 = 3np-2nP = nP$,

$ind R_2 = 3np +2nP =5nP$.

Пусть индексы вычетов $R_3$ и $R_4$ равны соответственно:

$ind R_3 = 3nP-m_1P$,

$ind R_4 = 3nP + m_1P$, где $m_1$ - натуральное число, тогда сравнение (4) будет

$g^{3nP-m_1P} + g^{3nP + m_1P}\equiv 1\mod P^2$, умножим, полученное сравнение,

на $g^ {m_1P}$ и принимая $g^{3nP}\equiv -1\mod P^2$ получим

$g^ {3nP}-g^{2m_1P}\equiv g^{m_1P}\mod P^2$ или

$-1-g^{2m_1P}-g^{m_1P}\equiv 0\mod P^2$, тогда


$g^{3m_1P}\equiv 1\ equiv g^{6nP}\mod P^2$, отсюда

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

$g^{m_1P}\equiv g^{2nP}\mod P^2$ или

$g^{m_1P}\equiv g^{4nP}\mod P^2$, но тогда

$ind R_3 = 3nP-m_1P = 3nP-2nP = nP = ind R_1$,

$ind R_4 = 3nP + m_1P = 3nP + 2nP = 5nP = ind R_2$ или

$ind R_3 = 3nP-m_1P = 3nP-4nP = - nP = 5nP-6nP = ind R_2$,

$ind R_4 = 3nP + m_1P = 3nP + 4nP = 7nP =6nP +nP = ind R_1$.

Пришли к противоречию .Вычеты $R_3$ и $R_4$ равны вычетам $R_1$ и $R_2$.

Следовательно, только вычеты $R_1$ и $R_2$ удовлетворяют условию (1).

Ну а если?

$ind R_3 = 3nP-m_1P$, а

$ind R_4 = 3nP + m_2P$, где

$m_1P$ не равно $m_2P$.

К сожалению, ответ на этот вопрос я не нашел. А потому прошу помочь доказать, что не

существует вычетов $R_3 и R_4$ индексы которых

$ind R_3 = 3nP-m_1P$,

$ind R_4 = 3nP + m_2P$ и сумма

$R-3 + R_4\equiv 1\mod P^2$, где $(m_1,m_2) є N^+$.




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

1.Обратим внимание, что в этом случае в системе {R} нет вычетов, принадлежащих

показателям 3 и 6, так как функция Эйлера

$\varphi (P^2) = (P-1) P = (6n +4)(6n + 5) =(6n + 4)P$ не делиться на 3 и 6, а

$ind (-1) = (6n + 4)P|2 = (3n + 2)P$.

2.Пусть существуют в системе {R} пара вычетов $U_3$ и $U_4$ таких, что

$U_3 + U_4\equiv 1\mod P^2\engo(4)$.

3.Принимаем условие симметричности индексов вычетов $U_3 и U_4$ относительно

индекса $ ind (-1) = (3n + 2)P$, тогда пусть

$U_3\equiv g^{(3n + 2)P -m_1P}\mod P^2$,

$U_4\equiv g^{(3n + 2)P +m_1P}\mod P^2$.

Тогда сравнение (4) запишем

$ g^{(3n + 2)P -m_1P} + g^{(3n + 2)P +m_1P}\equiv 1\mod P^2$, а после умножения

полученного сравнения, на $g^{m_1P}$ и принимая $ (-1)\equiv g^{(3n + 2)P}\mod P^2$

получим.

$g^{2m_1P} + g^{m_1P} +1\equiv 0\mod P^2$, тогда будет справедливо сравнение

$g^{3m_1P} -1\equiv 0\mod P^2$, отсюда следует, что вычет

$g^{m_1P}$ принадлежит

показателю 3, что невозможно, так как функция Эйлера не делиться на 3.

4. А если индексы вычетов $U_3$ и $U_4$ несимметричны относительно

индекса $ ind (-1) = (3n + 2)P$, тогда доказать отсутствие таких вычетов мне не

удалось. Прошу помочь разобраться с Утверждением 2.

[nnosipov]

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

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

Если простое число $P = 6n + 5$, то в системе {R} нет ни одной пары вычетов,

удовлетворяющих условию (1).

Это утверждение неверно. Наименьший контрпример --- $P=59$.

-- Вс июл 27, 2014 16:46:28 --

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

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

Если простое число $P = 6n + 1$, то в системе {R} имеются только 2(два) вычета,

Обозначим их как $R_1$ и $R_2$ таких, что $R_1 + R_2\equiv 1\mod P^2\engo(1)$.

Это также неверно (в том, что касается единственности указанной пары вычетов). Наименьший контрпример --- $P=79$. См. также topic76413.html

Для проверки подобных гипотез используйте компьютер.

[vasili]

Уважаемый nnosipov! Я благодарен Вам за отклик, который помог мне избавиться от многолетних заблуждений.

[vasili]

Уважаемые участники форума! Уважаемый nnosipov!

Я получил от nnosipov блестящий ответ на поставленную мною задачу.

Если администратор не возражает, то я несколько усложню задачу, а именно:

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

$r_1 - r_1r_3\equiv 1\mod P^2\engo (1)$,

$r_2 - r_2r_1\equiv 1\mod P^2\engo (2)$,

$r_3 - r_3r_2\equiv 1\mod P^2\engo (3)$,


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

$r_2^P - r_2^Pr_1^P\equiv 1\mod P^2\engo (5)$,

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


$r_1r_2r_3\equiv -1\mod P^2\engo (7)$ и

$r_1^Pr_2^Pr_3^P\equiv -1\mod P^2\engo (8)$, где

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

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

[nnosipov]

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

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

При любом $P \equiv 1 \pmod{6}$ эта система, наоборот, разрешима. И при $P \equiv -1 \pmod{6}$ она тоже может быть разрешимой (например при $P=59$).

Ещё раз предлагаю использовать компьютер. А также вчитаться в моё сообщение из topic76413.html

[vasili]

Уважаемый nnosipov! Приведенный Вами контр пример для P =59, а именно:
$r_1 =4$, $r_2 =39$ и $r_3 =45$ не удовлетворяет как минимум сравнению (7), так как

$r_1r_2r_3 =7020\equiv 58\mod 59^2 = 3481$, в тоже время

$r_1^{59}r_2^{59}r_3^{59}\equiv -1\mod 59^2$ удовлетворяют (8), где

$r_1^{59} =4^{59}\equiv 299\mod 59^2$,

$r_2^{59} = 39^{59}\equiv806\mod 59^2$,

$r_3^{59} = 45^{59}\equiv 1107\mod 59^2$

[nnosipov]

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

Приведенный Вами контр пример для P =59, а именно:
$r_1 =4$, $r_2 =39$ и $r_3 =45$ не удовлетворяет как минимум сравнению (7)

Но это только один из контрпримеров, есть и другие. Найдите такой, который удовлетворяет всем восьми сравнениям Вашей системы. Напишите для $P=59$ простенькую программу перебора всех троек остатков, проверяющую выполнимость сравнений системы. Делов-то на пять минут.

[vasili]

Уважаемый nnosipov!

В поисках решения сравнения (7) т.е. $r_1r_2r_3\equiv-1\mod 59^2$ я рассмотрел 3(три) класса

вычетов по модулю $P^2$, а именно:

- класс вычетов вида $R\equiv g^m\mod P^2$ ,

- класс вычетов $R\equiv g^{mP}\mod P^2$ и

-класс вычетов $R\equiv g^{kP + m}\mod P^2$, где

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

$k =1,2,3,\cdots\,(P-2)$,

$m = 1,2,3,\cdots\,(P-1)$.

1.Пусть $r_1$, $r_2$, $r_3$ принадлежат классу вычетов вида $R\equiv g^m\mod P^2$, .

тогда числа $r_1$, $r_2$, $r_3$ не удовлетворяют сравнению (7), так как

$ind r_1r_2r_3 < 3P$, а $ind (-1) = {\frac{P-1}{2}}P$, отсюда для всех $P >5$

$ind (-1) > ind r_2r_2r_3$.

2. Пусть $r_1$, $r_2$ $r_3$ принадлежат классу вычетов вида $R\equiv g^{mP}\mod P^2$,

( сь.. ниже Таблицу таких вычетов),

тогда для $P=59$

имеем нижеследующие четыре тройки решений сравнения (7):

1-я тройка
$r_1 =299$,
$r_2 = 806$,
$r_3 =1107$,


2-ая тройка $r_1 = 300$,
$r_2 = 1106$,
$r_3 =1405$,


3-я тройка
$r_1 = 3183$,
$r_2 = 2375$,
$r_3 =2676$,


4-я тройка
$r_1 = 3182$,
$r_2 = 2376$,
$r_3 =2077$,

т.е. $r_1r_2r_3 = 299\times806\times1107\equiv -1\mod 59^2$,
$r_1r_2r_3 = 300\times1106\times1405\equiv -1\mod 59^2$,
$r_1r_2r_3 = 3183\times2375\times2676\equiv -1\mod 59^2$,
$r_1r_2r_3 = 3182\times2376\times2077\equiv -1\mod 59^2$.

При этом $r_i^{59}\equiv r_i\mod 59^2$, так как

$r_i^{59}\equiv (g^{59m})^{59}\equiv (g^{(59-1)m})^{59}g^{59m}\mod 59^2$, отсюда

$ r_i^{59}\equiv r_i\equiv g^{59m}\mod 59^2$.


3. Пусть $r_1$, $r_2$, $r_3$ принадлежат классу вычетов вида $R\equiv g^{kP +m}\mod P^2$, т.е. .
$r_1\equiv g^{k_1P + m_1}\mod P^2$,

$r_2\equiv g^{k_2P + m_2}\mod P^2$,

$r_3\equiv g^{k_3P + m_3}\mod P^2$, тогда

$r_1r_2r_3\equiv g^{(k_1 +k_2 +k_3)P +m_1 +m_2 +m_3}\equiv g^{\frac{P-1}{2}}^P$, отсюда

$(k_1 + k_2 + k_3)P +m_1 +m_2 +m_3 = {\frac{P-1}{2}}P$, отсюда

$m_1 +m_2 +m_3 = 2P или (= P)\engo(1)$, так как $(m_1,m_2,m_3) < P$, тогда

$(k_1 + k_2 + k_3)P +2P или(+P)= P(k_1 + k_2 + k_3 + 2) = (1,3,5){\frac{P-1}{2}}P\engo(2)$,

Из (1) и (2) следует, что комбинации $k_i, m_i$ образующие тройки чисел $r_1,r_2, r_3$,

удовлетворяющих сравнению (7) исчисляется величиной (P-1)(P-2) (1,3,5), а значит

количество таких троек как минимум больше 4 для простого показателя $P =59$

Однако количество троек $r_1^P,r_2^P, r_3^P$, удовлетворяющих (7) для простого показателя $P =59$ равно 4.


Прошу помочь разобраться с п.3.










Таблица вычетов по модулю $59^2$, индексы которых кратные 59

Чтобы не загромождать текст, опущен символ $\mod 59^2$ и $\equiv$ заменен на $= $

$2^59 = 946$,

$(2^2) ^59 = 299$,

$(2^3) ^59 =893$,

$(2^4) ^59 = 2376$,

$(2^5) ^59 = 2451$,

$(2^6) ^59 = 300$,

$(2^7) ^59 = 1839$,

$(2^8) ^59 = 2675$,

$(2^9) ^59 = 3344$,

$(2^10) ^59 = 2676$,

$(2^11) ^59 = 809$,

$(2^12) ^59 = 2975$,

$(2^13) ^59 = 1702$,

$(2^14) ^59 = 1870$,

$(2^15) ^59 = 672$,

$(2^16) ^59 = 2170$,

$(2^17) ^59 = 2511$,

$(2^18) ^59 = 1364$,

$(2^19) ^59 = 2374$,

$(2^20) ^59 = 559$,

$(2^21) ^59 = 3183$,

$(2^22) ^59 = 53$,

$(2^23) ^59 = 1404$,

$(2^24) ^59 = 1923$,

$(2^25) ^59 = 2076$,

$(2^26) ^59 = 612$,

$(2^27) ^59 = 1106$,

$(2^28) ^59 = 1976$,

$(2^29) ^59 = 3480 = -1$,

$(2^30) ^59 = 2535$,

$(2^31) ^59 = 3182$,

$(2^32) ^59 = 2588$,

$(2^33) ^59 = 1105$,

$(2^34) ^59 = 1030$,

$(2^35) ^59 = 3181$,

$(2^36) ^59 = 1645$,

$(2^37) ^ 59 = 806$,

$(2^38) ^59 = 137$,

$(2^39) ^59 = 805$,

$(2^40) ^59 = 2672$

$(2^41) ^59 = 506$,

$(2^42) ^59 = 1779$,

$(2^43) ^59 = 1611$,

$(2^44) ^59 = 2809$,

$(2^45) ^59 =1311$,

$(2^46) ^59 = 970$,

$(2^47) ^59 = 2117$,

$(2^48) ^59 = 1107$,

$(2^49) ^59 = 2922$,

$(2^50) ^59 = 298$,

$(2^51) ^59 = 3428$,

$(2^52) ^59 = 2077$,

$(2^53) ^59 = 1558$

$(2^54) ^59 = 1405$,

$(2^55) ^59 = 2869$,

$(2^56) ^59 = 2375$,

$(2^57) ^59 = 1505$,

$(2^58) ^59 = 1$,

[nnosipov]

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

Однако количество троек $r_1^P,r_2^P, r_3^P$, удовлетворяющих (7) для простого показателя $P =59$ равно 4.

Троек $(r_1,r_2,r_3)$ много, а троек $(r_1^P,r_2^P,r_3^P)$ мало. И в чём противоречие?

[vasili]

Уважаемый nnosipov!
$r_1r_2r_3\equiv -1\mod P^2$ - много, а

$r_1^Pr_2^Pr_3^P =(r_1r_2r_3)^P\equiv (-1)^P\mod P^2$- мало.

В этом я усмотрел противоречие.

[nnosipov]

Это противоречие из разряда тех, когда в огороде много бузины, а в Киеве мало дядек. Разумеется, если тройка $(r_1,r_2,r_3)$ удовлетворяет сравнению $r_1r_2r_3 \equiv -1 \pmod{P^2}$, то она же удовлетворяет и сравнению $r_1^Pr_2^Pr_3^P \equiv -1 \pmod{P^2}$. Именно поэтому в Вашей системе сравнений восьмое сравнение можно спокойно убрать --- оно автоматически выполняется.

Вот решение системы при $P=59$: $r_1=4$, $r_2=1160$, $r_3=871$.

[vasili]

Уважаемый nnosipov! Нельзя не согласиться с Вашим откликом.Вы предложили пример

$r_1 =4$, $r_2 = 19\times59 +39$, $r_3 =14\times59 + 45$, удовлетворяющий всем

сравнениям. Хотел лишь обратить внимание, что тройка чисел

$r_1^{59} =299$, $r_2^{59} =806$, $r_3^{59} = 1107$ удовлетворяет всем тройкам

$r_1= 4$, $r_2 =59 k + 39$ и $r_3 = 59k + 45$, где $k = 1,2,3\cdots\,58$.

Отсюда и возникло у меня "мало" и "много".