Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 19 ]  На страницу Пред.  1, 2
Автор Сообщение
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 30 окт 2019, 18:32 
Не в сети
Оракул
Зарегистрирован:
17 апр 2019, 04:57
Сообщений: 709
Откуда: грузия
Cпасибо сказано: 58
Спасибо получено:
12 раз в 12 сообщениях
Очков репутации: -6

Добавить очки репутацииУменьшить очки репутации
Kак определяется число "чистых" разностей?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 10 ноя 2019, 21:53 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
***


Последний раз редактировалось vorvalm 10 ноя 2019, 21:57, всего редактировалось 1 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 10 ноя 2019, 21:56 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
ammo77 писал(а):
Kак определяется число "чистых" разностей?

Этот вопрос является самым сложным в этой теме, т.к. включает в себя
новые предикаты, которые надо разбирать отдельно.
Будем считать, что функции Эйлера высших порядков вкратце мы разобрали.
Теперь разберемся с коэффициентом [math]A_n[/math]
Для этого потребуются еще две функции
1) функция [math]m(p)[/math] - число вычетов группы (кортежа), сравнимых
с каким-либо другим вычетом по простому модулю [math]p[/math], входящему в состав модуля [math]M[/math]
Например, группа [math]D(10)=(4,2,4)[/math] или приведенная группа (паттерн) [math]D[4]=(0,4,6,10).[/math]
Здесь имеем два сравнимых вычета по модулю [math]p=3[/math], это 0,6 и 4,10, т.е. [math]m(3)=2[/math]
По модулю [math]p=5[/math] имеем один вычет 0,10, т.е. [math]m(5)=1[/math].
Это означает, что число вычетов [math]n[/math] в функции Эйлера [math]n[/math]-го порядка [math]\varphi_n(p)=p-n[/math]
уменьшается на величину [math]m(p)[/math], т.к. сравнимые вычеты по модулю [math]p[/math] являются одним вычетом.
Но это будет уже не функция Эйлера, а новая функция
2) [math]K(p) = p - (n - m(p)) = p +m(p) -n[/math]
Эта функция определяет число групп в ПСВ по модулю [math]p[/math]
В нашем примере [math]K(3)=3+2-4=1,\;K(5)=5+1-4=2[/math]
При этом функции Эйлера по этим модулям равны
[math]\varphi_4(3)= 1 (p<n),\;\varphi_4(5)= 5-4 =1.[/math]
Как видим по модулю [math]p=3[/math] функции [math]K(3)[/math] и [math]\varphi_4(3)[/math] совпадают, но по модулю [math]p=5[/math] нет.
Поэтому в функции [math]\varphi_4(M)[/math] надо заменить [math]\varphi_4(5)[/math] на [math]K(5)[/math]
Получим формулу числа групп [math]D(10)=(4,2,4)[/math]
[math]N(D(10))=2\varphi_4(M)[/math]
Итак, мы нашли [math]A_4=2[/math] для группы [math]D(10).[/math]. По модулю [math]M=30[/math] имеем две группы [math](4,2,4)[/math]
[math]7, 11, 13, 17[/math] и [math]13, 17, 19, 23[/math].
Но самое интересное заключается в том, что если по какому-либо модулю функция [math]K(p)=0[/math], то это
означает, что данная группа (кортеж) не существует в ПСВ по данному модулю и во всех последующих.
Поэтому первое назначение функции [math]K(p)[/math] определять, есть ли такие группы в ПСВ.
Присвоим функции [math]K(p)[/math] имя "проходимость" группы по данному модулю.
Второе назначение этой функции определять коэффициент [math]A_n[/math]
Функция [math]K(p)[/math] является мультипликативной, т.е. [math]K(p_s)K(p_t)=K(p_sp_t)[/math], отсюда
функция [math]K(M)[/math] фактически определяет число групп (кортежей) в ПСВ по модулю [math]M=p\#[/math].
Но такие вычисления будут нерациональны, т.к. придется вычислять [math]K(p)[/math] по всем простым модулям,
входящим в модуль [math]M[/math]. Поэтому будем вычислять [math]K(p)[/math] только по тем простым модулям,
по которым могут сравниваться вычеты группы (кортежа). Они как, правило, отличаются от соответствующих
функций Эйлера по этим же модулям, но могут быть и равны. В любом случае надо полученные [math]K(p)[/math]
поставить на место соответствующих функций Эйлера по тем же простым модулям в функции [math]\varphi_n(M)[/math].
Функции [math]K(p)[/math] и [math]\varphi_n(p)[/math] мультипликативные и мы можем объединить их в произведения

[math]\prod K(p)[/math] и [math]\prod\varphi_n(p)[/math]

Отсюда число групп n-го порядка будет равно

[math]N=\frac{\varphi_n(M)}{\prod\varphi_n(p)}\cdot\prod K(p)=\frac{\prod K(p)}{\prod\varphi_n(p)}\varphi_n(M)= A_n\varphi_n(M)[/math]. т.е. [math]A_n=\frac{\prod K(p)}{\prod\varphi_n(p)}[/math]

По этой формуле можно вычислять число данных групп по модулю [math]M>p\#[/math], т.к. при меньших [math]M[/math]
число групп определяется по [math]K(p)[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 05 дек 2019, 11:21 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
Чтобы перейти от формулы "нечистых" разностей к формуле "чистых" разностей,
надо разделить группы вычетов (кортежи) не только по числу вычетов в группе
и разностям между вычетами, но и по другим признакам.
В ПСВ есть группы вычетов, у которых максимальное число вычетов при данной
общей разности между последним и первым вычетами.
Такие группы будим называть первообразными
Все другие группы с данной общей разностью, но с меньшим числом вычетов и
входящие в состав первообразной группы будем называть производными.
Иными словами, производные группы получаются исключением вычетов из
первообразной группы.
Например, группа [math]F(16)=(4,2,4,2,4)[/math] является первообразной, т.к. при общей разности 16
больше 6 вычетов в группе быть не может. Исключая по одному вычету из группы, получим
4 производных групп [math]E(16)=(6,4,2,4)=(4,6,2,4)=(4,2,6,4)=(4,2,4,6)[/math] первого порядка.
Исключая по одному вычету в этих группах, получим 6 производных групп второго порядка.
[math]D(16)=(10,2,4)=(6,6,4)=(6,4,6)=(4,8,4)=(4,6,6)=(4,2,10)[/math], далее 4 группы третьего порядка
[math]C(16)=(12,4)=(10,6)=(6,10)=(4,12)[/math] и, наконец, одна группа четвертого порядка [math]B(16[/math]).
Это уже "чистая" разность между вычетами ПСВ.
Как видим,"чистые" разности являются последними производными группами и образуются в ПСВ по мере
роста модуля [math]M=p\#[/math]. Вроде все просто. Надо из общего числа разностей вычесть число всех
производных и первообразных групп. Следовательно, нам надо найти все эти группы, начиная с первообразной.
Поиск первообразной группы представляет определенную трудность.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 26 дек 2019, 10:15 
Не в сети
Начинающий
Зарегистрирован:
30 ноя 2019, 08:51
Сообщений: 26
Cпасибо сказано: 0
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Как доказать, что данная группа первообразная ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 29 дек 2019, 15:11 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
По определению первообразная группа (кортеж) состоит
из максимально возможного числа вычетов при данной общей разности.
Наличие любых групп в ПСВ определяется "проходимостью" этих групп.
Этот предикат подробно рассмотрен в закрытой теме " ПСВ и аддитивные
проблемы простых чисел".
Проходимость группы функция двух переменных.
1) Модуль (простое число [math]p[/math]), по которому сравниваются вычеты группы и
2) число вычетов в группе ([math]n[/math])

[math]K(p)= p +m(p)-n[/math]

[math]m(p)[/math] - число вычетов группы, сравнимых по модулю [math]p[/math]

Группа "проходит" в ПСВ, если [math]K(p)>0[/math].

Самым надежным способом определения первообразных групп является представление данной
общей разности в виде группы с разностями между вычетами группы (2,4,2,4...) или (4,2,4,2...)
и путем последовательного удаления вычетов найти такой состав вычетов, когда K(p)>0
При общей разности [math]d>16[/math] поиск первообразных групп представляет
определенные трудности. Даже при разности [math]d=14[/math] есть проблемы.
Покажем на примере разности [math]d=14[/math] поиск первообразной группы.
По аналогии с группой [math]F(4,2,4,2,4)[/math] создадим группу [math]F(2,4,2,4,2)[/math]
общая разность которой равна [math]d=14[/math].
Проверяем эту группу на проходимость.
Приведенная группа [math]F[6]=(0,2,6,8,12,14)[/math]. Число вычетов [math]n=6[/math]..
Проходимость по модулю [math]p=3,\;K(3)=3+m(3)-6.[/math]
Имеем 4 вычета, сравнимых по модулю [math]p=3[/math], т.е. [math]m(3)=4[/math]
[math]K(3)=3+4-6=1[/math].
Проходимость по модулю [math]p=5,\;K(5)=5+m(5)-6[/math]
Имеем один вычет, сравнимый по модулю [math]p=5[/math], т.е. [math]m(5)=1[/math]
[math]K(5)=5+1-6=0[/math]
Группа не проходит по модулю [math]p=5.[/math] Что делать?
Надо искать группу с общей разностью [math]d=14[/math] с меньшим числом вычетов.
Далеко ходить не будем. Возьмем группу [math]F[6]=(0,2,6,8,12,14)[/math] и находим все
производные группы первого порядка. Получим 4 группы 5-го размера.

[math]E[5]=(0,6,8,12,14),\;(0,2,8,12,14),\;(0,2,6,12,14),\;(0,1,6,8,14)[/math]

Если первообразная группа "проходит" по какому-либо модулю, то производные от нее
группы также проходят по этому модулю, т.е. проверять их на проходимость по этому модулю не надо.
Из 4-х групп по модулю [math]p=5[/math] проходят только две, имеющие вычеты [math]2[/math] и [math]12[/math]
Т.е. первообразными группами с общей разностью [math]d=14[/math] являются

[math]E[5]=(0,2,8,12,14)[/math] и [math](0,2,6,12,14)[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 11 янв 2020, 19:31 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
Продолжение предыдущего поста.
* * *
Аналогично можно найти первообразные группы для любой разности, но с увеличением этой
разности возрастает и число производных групп.
Число групп (кортежей) [math]Q[n]\; \; n[/math] - го размера в ПСВ определяется формулой

[math]N(Q[n])=A_n\varphi_n(M)[/math]

Эта формула дает точный результат только для первообразных групп.
При определении числа производных групп первого порядка эта формула даст
общее число этих групп, куда войдут:
1) собственно производые группы,
2) те же группы, но которые входят в состав первообразных
Например, если определять число разностей [math]d=6[/math] по формуле [math]N(6)=2\varphi_2(M)[/math]
в ПСВ(30), то получим [math]N(6)=2\cdot 3=6[/math]. Это разности
[math]7-1,\;\;13(11)-7,\;\;17(13)-11,\;\;19(17)-13,\;\;23(19)-17,\;\;29-23.[/math]
Из них только две являются "чистыми" разностями [math](7-1)[/math] и ([math]29-23[/math]).
Остальные являются группами [math]C(4,2),\;\;C(2,4)[/math], которые
для группы B(6) являются первообразными.
Вывод напрашивается сам. Число первых производных групп определяется как
разность между общим числом этих групп и числом первообразных групп

Обозначим первообразные группы [math]Q[n][/math] размером [math]n[/math] (число вычетов в группе),
тогда первые производные от этих групп будут [math]Q[n-1].[/math] Число их в ПСВ(М) равно

[math]N(Q[n-1])=A_{n-1}\varphi_{n-1}(M)-A_{n}\varphi_{n}(M)[/math] где

[math]A_{n-1},\;A_n[/math] - суммарные коэффициенты проходимости по всем группам [math]Q[n-1],\;Q[n][/math]

Число вторых производных групп [math]Q[n-2][/math] равно разности между общим числом
этих групп и числом первых производных групп [math]Q[n-1].[/math]

[math]N(Q[n-2])=A_{n-2}\varphi_{n-2}(M)-N(Q[n-1])[/math]=

[math]A_{n-2}\varphi_{n-2}(M)-A_{n-1}\varphi_{n-1}(M)+A_{n}\varphi_{n}(M)[/math]

В общем случае, когда группа [math]B(d)[/math] (последовательная разность [math]d[/math]) является
производной группой от первообразной [math]n[/math]-го размера, число их равно

[math]N(B(d))=\sum_2^n(-1)^nA_n\varphi_n(M)\;\;\;M\geqslant p\#[/math] где

[math]p[/math] - наибольший модуль сравнения вычетов первообразной группы,
[math]A_n[/math] - суммарные коэффициенты проходимости для всех групп одного размера.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 07 фев 2020, 12:23 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
Пример определения числа "чистых" разностей [math]d = 14 (B(14))[/math] в ПСВ.
Первообразные группы были определены ранее:
[math]E[5] = (0,2,8,12,14)[/math] и [math]E[5] = (0,2,6,12,14)[/math]
У каждой группы есть по три вычета, сравнимых с [math]p =3[/math] и по одному вычету,
сравнимому с [math]p = 5[/math] и [math]p = 7.[/math]
Отсюда проходимости каждой групп равны.
[math]K(3) = 3 + 3 – 5 = 1, K(5) = 5 + 1 – 5 = 1, K(7) = 7 + 1 – 5 = 3.[/math]
Суммарный коэффициент проходимости для 2-х групп [math]E[5][/math]

[math]A_5 = 2 \prod \frac{K(p)} { \varphi_5(p)} = 2 \frac {1\cdot1\cdot3} { 1\cdot1\cdot 2} = 3.[/math]

Находим первые производные группы (повторные группы не учитываем).
[math]D[4] = (0,8, 12,14), (0,2 ,12,14), (0,2,8,14), (0,6,12,14), (0,2, 6,14), (0,6,8,14)[/math]
Первые 5 групп взяты от 2-х первообразных, но 6-я группа взята от группы,
не прошедшей по модулю [math]p = 5.[/math]
У каждой группы есть по два вычета , сравнимых с [math]p = 3[/math] и по одному вычету,
сравнимому с [math]p = 7.[/math] У одной группы есть один вычет, сравнимый с [math]p = 5[/math], но у остальных нет таких .вычетов.
Отсюда проходимости каждой групп равны.
[math]K(3) = 3 + 2 – 4 = 1, K(7) = 7 + 1 – 4 = 4.[/math] Для 5-ти групп [math]K(5) = 5 + 0 – 4 = 1.[/math]
Для одной [math]K(5) = 5 +1 – 4 = 2.[/math]. Суммарный коэффициент всех групп [math]D[4][/math] равен

[math]A_4 = 5 \prod \frac{K(p)} {\varphi_4(p)} + \prod\frac{ K(p)}{\varphi_4(p)} = 5 \frac{1\cdot1\cdot4}{1\cdot1\cdot3}+\frac{1\cdot2\cdot4}{1\cdot1\cdot3}=\frac{28} { 3}.[/math]

Находим вторые производные группы.
[math]C[3] = (0,2,14), (0,6,14), (0,8, 14), (0,12, 14)[/math]
У каждой группы есть по одному вычету, сравнимому с [math]p = 3[/math] и [math]p = 7,[/math]
но сравнимых с [math]p = 5[/math] нет.
Отсюда проходимость каждой группы равна
[math]K(3) = 3 +1 – 3 = 1, K(5) = 5 + 0 – 3 = 2, K(7) = 7 + 1 – 3 = 5.[/math]
Суммарный коэффициент проходимости всех групп [math]C[3][/math] равен:

[math]A_3 = 4 \prod\frac{ K(p)}{ \varphi_3(p)} = 4 \frac{1\cdot 2\cdot 5}{1\cdot 2\cdot 4} = 5[/math]

Осталась одна производная 3-го порядка [math]D[14] = (0,14)[/math] ("Чистая разность")
. Ее проходимости по модулям [math]p=3,\;p=5,\;p=7[/math]
[math]K(3) = 3 + 0 – 2 = 1, K(5) = 5 + 0 – 2 = 3, K(7) = 7 + 1 – 2 = 6.[/math], отсюда

[math]A_2 = \prod\frac {K(p)}{ \varphi_2(p)} =\frac{ 1\cdot3\cdot6}{ 1\cdot 3\cdot 5} = \frac 6 5[/math]

Окончательно получаем формулу числа «чистых» разностей [math]d = 14[/math] в ПСВ(М).

[math]N(B[14]) = \frac 6 5\varphi_2 – 5\varphi_3 + \frac{28} 3\varphi_4 – 3\varphi_5[/math] (аргумент М опущен)

Проверка формулы при [math]M = 7\# = 210[/math]
[math]\varphi_2(M) = 15,\; \varphi_3(M) = 8, \;\varphi_4(M) = 3,\; \varphi_5(M) = 2[/math],

[math]N(B[14]) = 15\cdot\frac 6 5 – 5\cdot 8 + 3\cdot \frac{28} 3 – 3\cdot 2 = 18 – 40 + 28 - 6 = 0.[/math]
В ПСВ(210) чистых разностей [math]d = 14[/math] нет.

Проверка при [math]M = 11\# = 2310[/math]
[math]\varphi_2 (M) = 135, \varphi_3(M) = 64, \varphi_4(M) = 21, \varphi_5(M) = 12.[/math]

[math]N(B[14]) = 135\cdot\frac 6 5 – 5\cdot 64 + 21\cdot\frac {28} 3 - 3\cdot 12 = 162 - 320 + 196 – 36 = 2.[/math]
В ПСВ(2310) чистых разностей [math]d = 14[/math] всего 2.
Это знаменитая разность [math]127 – 113 = 14[/math] и [math]2197 – 2183 = 14.[/math]

Приведем без доказательства некоторые формулы числа последовательных разностей между вычетами ПСВ. Аргумент М опущен.

[math]N(6) = 2\varphi_2 – 2\varphi_3,[/math]
[math]N(8) = \varphi_2 – 2\varphi_3 + \varphi_4,[/math]
[math]N(10) = \frac 4 3\varphi_2 – 3\varphi_3 + 2\varphi_4[/math]
[math]N(12) = 2\varphi_2 – 7\varphi_3 + 10\varphi_4 -2\varphi_5.[/math]
[math]N(16) =\varphi_2-5\varphi_3+12\varphi_4-6\varphi_5+\varphi_6[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Приведенные системы вычетов
СообщениеДобавлено: 22 фев 2020, 10:18 
Не в сети
Light & Truth
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3379
Cпасибо сказано: 47
Спасибо получено:
476 раз в 440 сообщениях
Очков репутации: 19

Добавить очки репутацииУменьшить очки репутации
***

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.    На страницу Пред.  1, 2  Страница 2 из 2 [ Сообщений: 19 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Приведенные системы вычетов их Диагонализация

в форуме Размышления по поводу и без

ammo77

0

29

22 фев 2020, 11:31

Системы линейных уравнений. Однородные системы

в форуме Линейная и Абстрактная алгебра

Mark2

8

412

27 апр 2014, 18:56

Вычислить интеграл(без вычетов)

в форуме Комплексный анализ и Операционное исчисление

aleksandrannn

1

188

22 дек 2014, 21:06

Обратимость в кольцах вычетов

в форуме Линейная и Абстрактная алгебра

fingolfin

19

452

29 мар 2018, 14:19

Интеграл с помощью вычетов

в форуме Комплексный анализ и Операционное исчисление

tanyhaftv

1

158

05 авг 2018, 00:04

Интеграл с помощью вычетов

в форуме Комплексный анализ и Операционное исчисление

Aizh

27

875

27 янв 2014, 18:24

Интеграл с помощью вычетов

в форуме Комплексный анализ и Операционное исчисление

Wersel

2

278

26 янв 2014, 06:15

Вычислить с помощью вычетов

в форуме Комплексный анализ и Операционное исчисление

MAZBELAZ

17

609

08 янв 2014, 18:51

Вычислить интеграл при вычетов

в форуме Комплексный анализ и Операционное исчисление

photographer

1

187

11 июл 2016, 22:08

Вычислить с помощью вычетов

в форуме Комплексный анализ и Операционное исчисление

Sasha95

7

449

02 дек 2013, 21:14


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  
cron

Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved