Проблемы аддитивной теории простых чисел

Автор темы vorvalm 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеПреподаватель мехмата МГУ удостоен международной премии по математике Presburger Award28.07.2020 01:04
05.12.2019 12:15
ПСВ
Невычеты ПСВ -
- простые числа, составляющие модуль ПСВ ($p_r\#$) и кратные им
числа меньше модуля.
Общее число их В ПСВ равно $M(p_r)-\varphi(M),$ т.е. множество чисел
праймориала включает в себя вычеты ПСВ и невычеты ПСВ.
В свою очередь вычеты ПСВ состоят из простых и взаимно простых с модулем чисел.
Невычеты образуют классы чисел, не превосходящих модуль: $(n\in N)$
1) кратные $p=2,\;\;a_n=2n,$
2) кратные $p=3,\;\;a_n=3+6(n-1),$
3) кратные $p=5,$ cуперпозиция двух классов,
$a_n=5+30(n-1)$
$a_n=25+30(n-1)$
4) кратные $p=7,$ cуперпозиция 8-ми классов (ПСВ(30)),
$a_n=7+210(n-1)$
$a_n=49+210(n-1)$
$a_n=77+210(n-1)$
$a_n=91+210(n-1)$
$a_n=119+210(n-1)$
$a_n=133+210(n-1)$
$a_n=161+210(n-1)$
$a_n=203+210(n-1)$
5) кратные $p=11,$ cуперпозиция 48-ми классов (ПСВ(210)),
$a_n=11+2310(n-1)$
..........................................................................
..........................................................................
$a_n=2299+2310(n-1)$
6) кратные $p=13$. cуперпозиция 480-ти классов (ПСВ(2310)),
..........................................................................
7) кратные $p=17$ и т.д.

Вычеты ПСВ можно определять по формуле

$a_x=\mid \prod p_s^{\alpha_s}\pm\prod p_t^{\beta_t}\mid<M=\prod p_s\cdot p_t$
где $\alpha_s,\;\beta_t\in N.$

Порядковые номера вычетов здесь не определяются.

В чем преимущество рассмотрения закономерностей распределения
простых чисел с помощью ПСВ:
1) диапазон исследования ограничен модулем в отличии от
натурального ряда,
2) полная симметрия вычетов ПСВ относительно 0,5M

$M(p_r) - a_n=a_{\varphi(M)-n},$
3) в любой ПСВ есть интервал последовательных простых чисел

$1<p_{r+1}. . . . .p_n<p^2_{p_{r+1}}$
Определим, какую долю составляют простые числа среди вычетов ПСВ
по модулю $M=p_r\#.$
Число простых чисел в ПСВ по Чебышеву $\pi(M)-r\sim\frac M{lnM}$

Число вычетов ПСВ по Мертенсу $\varphi(M)\sim M\frac C{lnM}$

Их отношение $q$ = $\frac{\pi(M)-r}{\varphi(M)}\sim\frac{lnM}{ClnM}$, т.е. с ростом $p_r$ доля простых чисел в ПСВ уменьшается, но стремится к определенному пределу.
Практический расчет показывает следующий результат
М(7) = 210, q = 0,96
(11) 2310,- - - - 0,73
(13) 30030- - - -0,56
(17) 510510- - - -0,46
(19) 9699690- - -0,40
(23) 223092870- - 0,34



Редактировалось 1 раз(а). Последний 05.12.2019 12:16.
06.12.2019 08:23
простые числа
Кто то утверждал что прогрессии не пригодный для работы с факторизацией.

Кратности работають упорядочено а не в разбрось как показано.
06.12.2019 09:57
между прочим
загляни в личку...
13.04.2020 12:47
Функция Эйлера второго порядка
Для понимания роли функции Эйлера второго порядка в распределении вычетов ПСВ
вернемся немного назад к Бухштабу.
Полная система (ПС) вычетов по простому модулю $p$ образуется
из вычетов, взятых по одному из каждого класса по модулю р. Число их равно $p$.
Наименьшие натуральные вычеты ПС по модулю р: $1, 2, 3, .....p - 1, p.$
Вопрос. Сколько чисел в этой системе взаимно простых с модулем?
Из всех вычетов ПС только один р не взаимно простой с модулем р.
Отсюда число таких чисел равно $p - 1.$ Это и есть ПСВ по модулю р.
За основную ПСВ принимают ту, у которой натуральные вычеты меньше модуля.
Теперь переходим к более высокому порядку сортировки вычетов ПСВ.
Обозначим $a$ - вычет ПСВ, $d$ - четное число.
Вопрос. Сколько чисел $a + d$ взаимно простых с модулем $p$ и взаимно несравнимых
по модулю в ПСВ..
Оказывается, что число чисел $a + d$ в ПСВ зависит от разности $d.$
Если $(p,d)=1$, то число таких чисел равно $p-2=\varphi_2(p)$, ($p>2$)
Доказательство. Если $(p,d)=1$ и $p>d$, то $d=a_n$, т.е. является вычетом ПСВ(р) где всегда найдется
один вычет $a_m$, когда $a_m+a_n=a_m+d=p$ и $N(d)=\varphi(p)- 1=φ_2(p).$
Выражение $\varphi_2(p)=p-2$ назовем функцией Эйлера второго порядка по модулю $p$.
Если $p<d$, то $d=kp+a_n$ , ($a_n<p$) и $kp+a_n+a_m=p(k+1)$, т.е.$N(d)=φ_2(p)$.
Если $p|d$, то число этих чисел равно $p-1=\varphi(p).$.
Доказательство.
Если $p∣d$, то $d=kp$ и $a_n+kp$- вычет ПСВ(p), т.е. все вычеты ПСВ имеют разности $d$ и $N(d)=φ(p)$.
Необходимо доказать, что функции Эйлера второго порядка мультипликативна, и найти
формулу этой функции по составному модулю.



Редактировалось 1 раз(а). Последний 13.04.2020 12:58.
19.04.2020 11:50
: Функция Эйлера второго порядка
. Функция Эйлера второго порядка мультипликативная, т.е.

φ_2 (p_r p_s) = φ_2 (р_r) φ_2(р_s) = (р_r - 2)(р_s - 2)

Доказательство. Пусть х пробегает значения r_1,r_2,...r_j вычетов ПСВ по модулю р_r,
а у пробегает значения s_1,s_2,...s_i вычетов по модулю р_s.
Составим всевозможные числа вида хр_s + ур_r, соответствующих различным парам чисел r и s.

Число таких чисел равно φ(р_r)φ(р_s). Так как (р_r,р_s) = 1, то числа p_r s_i+р_s r_j образуют
ПСВ по модулю m = р_s p_r
Составим таблицу указанных чисел в следующем порядке:

p_r+p_s,.... 2p_r+p_s,............ .φ(p_r)p_r+p_s

p_r+2p_s,,,,,,, 2p_r+2_s,...............φ(p_r)p_t_+2p_s
............................................................
pr+φ(p_r)p_s,..... 2p_r+φ(p_r)p_s,..........φ(p_r)p_r+φ(p_r)p_s

Числа каждой строки являются ПСВ по модулю р_r, а числа каждой колонки являются ПСВ по модулю р_s.

Следовательно, в каждой строке и в каждой колонке есть по одному вычету такому, который не имеет своего близнеца.

При данном расположении чисел в таблице вычеты, не имеющие близнецов, составляют одну строку и одну колонку.

Любая строка и колонка имеют общий вычет, отсюда:

φ_2 (p_r p_s) = φ(р_r) (р_s) - (φ(р_s)) + 1 = (φ(р_r) - 1)(φ(р_s) - 1) =

φ_2(р_r) φ_2(p_s) = (р_r - 2)(р_s - 2)

На основании теоремы 3, полагая φ_2 (2) = 1, получим

φ_2 (М) = П φ_2 (р) =П (р – 2) ; р\М
20.05.2020 10:53
33
Volvram все вычеты тарабанить а порядок близнецов так и не нашел .

Я задал такой вопрос в мат-группах в соцсетях и на форумах >

Is there a connection with arithmetic progression and the meaning of Euler Functions. If there is what this connection is?

Есть ли связь с арифметической прогрессией и значением Функций Эйлера .Если есть то что это за связь?

Здесь Volvram описывет аж Функция Эйлера второго порядка, наверно может ответит и на такой простенький вопрос.


* Оказывается, что число чисел a+d в ПСВ зависит от разности d. " и как это ты смог докумекать ?

* Функция Эйлера второго порядка мультипликативная * не только второго а любого бесконечного n порядка мультипликативная и это аксиома .



Редактировалось 2 раз(а). Последний 20.05.2020 16:13.
20.05.2020 17:38
Функция Эйлера второго порядка
Теперь рассмотрим функцию Эйлера второго порядка по любому составному модулю.
Надо рассмотреть два случая нечетного и четного составного модуля.
Для нечетного составного модуля $m = p_s^{\alpha}\cdot p_t^{\beta}…$

$\varphi_2(m)=m\prod(1-\frac 2 p),\;\;$ где $p\mid m$

Для четного составного модуля $m =2^n p_s^{\alpha}\cdot p_t^{\beta}…$


$\varphi_2(m)=\frac 1 2 m\prod(1-\frac 2 p),\;\;$ где $p\mid m$ кроме р = 2.



Редактировалось 1 раз(а). Последний 20.05.2020 17:43.
20.05.2020 22:03
33
Молодец наконец то кое что понял ,уже и четные и нечетные осилил . Существенная разница год назад этой абстракции точно не било .
Комбинаций вычетов если еще соберешь то успех гарантрован .А так все это и великим известно било .Порядок близнецов ищи распределение по отдельним видам ,то что вернулся составним модулям похвально год назад ты говорил что от них все изученно. Прогрессии не забудь, без них грошь цена всем этим показам как ты любишь говорит :изобратешь велик десна 2:.
20.05.2020 22:42
33
http://www.bitman.name/math/article/226/332?fbclid=IwAR0oUhjKJL6CorljdcBavho8wSr5blslPs3ALBXedHClr5FSjDD52t83GHI

Посмотри как усердно трудяться италянцы что понять связь с прогрессиями и значениями Функции Эйлера , правда их такая статистика, думаю
для понимания этой связы не продвинулась ни на шаг.
Там попитка обьяснит в принципе эту связь но неправильный подход их запутал окончательно,то же самая ошибка как и с простыми числами.

Все ошибки и за непонимания остатков или более точно теория чисел нуждаеться в строгой классификаций чисел на виды ,без которых
невозможно показать закономерность простых чисел в натуральном ряде.



Редактировалось 2 раз(а). Последний 20.05.2020 23:12.
21.05.2020 17:26
: Функция Эйлера второго порядка
Для доказательства приведенных формул воспользуемся теоремой Бухштаба.

Во-первых, надо доказать формулу функции Эйлера второго порядка
для степени нечетного простого числа

$\varphi_2(p^n)=p^{n-1}\varphi_2(p)$

В ряду натуральных чисел от 1 до $p_n$ имеется $p^n|p =p^{n-1}$ чисел, кратных $p,$,
но по определению функции Эйлера второго порядка число пар вычетов,
у которых один из них кратен $p$ равно $2p^{n-1}$
Отсюда

$p^n - 2p^{n-1}= p^{n-1}(p-2)=p^{n-1}\varphi_2(p)= \varphi_2(p^n)$



Редактировалось 1 раз(а). Последний 28.05.2020 10:34.
25.05.2020 09:11
простые числа
787*157=123559
157*157=24649
123559 -24649=98910>98910/157=630
123559+24649=148208>149208/157=944

944+630=1574>2*787
944-630=314>2*157
314>314/100=π

1574/314=787/157=5.0127388535031847
π и вычеты.
Здесь формула закономерности вычета 157 для всех его произведении трлько двух простых 157*P любого диапазона .

https://www.facebook.com/photo.php?fbid=4095002023858185&set=gm.3041502899267181&type=3&theater&ifg=1



Редактировалось 3 раз(а). Последний 25.05.2020 09:35.
28.05.2020 10:36
: Функция Эйлера второго порядка
Докажем формулу функции Эйлера второго порядка для нечетных модулей.
$m=p_r^n p_s^t$


$\varphi_2(p_r^n)=p_r^{n-1}(p_r-2)$
$\varphi_2(p_s^t)=p_s^{t-1}(p_s-2)$

Так как функция Эйлера второго порядка мультипликативная, то

$\varphi_2(m)=\varphi_2(p_r^n)\varphi_2(p_s^t)=p_r^{n-1}p_S^{t-1}(p_r-2)(p_s-2)=m\prod(1-\frac 2 p),\;\;p|m$



Редактировалось 1 раз(а). Последний 29.05.2020 08:50.
28.05.2020 23:54
простые числа
Цитата
vorvalm
Докажем формулу Эйлера второго порядка для нечетных модулей.
$m=p_r^n p_s^t$


$\varphi_2(p_r^n)=p_r^{n-1}(p_r-2)$
$\varphi_2(p_s^t)=p_s^{t-1}(p_s-2)$

Так как функция Эйлера второго порядка мультипликативная, то

$\varphi_2(m)=\varphi_2(p_r^n)\varphi_2(p_s^t)=p_r^{n-1}p_S^{t-1}(p_r-2)(p_s-2)=m\prod(1-\frac 2 p),\;\;p|m$

Покажи числовое выражение твойх формул ,Функция Эйлера любая мультипликативная а не только 2 го порядка кстати что такое функция Эйлера второго порядка?
30.07.2020 10:51
Функция Эйлера второго порядка
Формула функции Эйлера второго порядка для четных модулей.



$m=2^k\cdot p_r^n\cdot p_s^t$



Здесь достаточно доказать, что $\varphi_2(2^k)=\frac 1 2\cdot 2^k$

Действительно, среди всех натуральных чисел от $1$до $2^k$ находятся $2^k|2=2^{k-1}$ чисел,

взаимно простых и несравнимых с $2^k$, т.е. нечетные числа.

И любые из этих чисел в сумме с четной разностью также взаимно простые и несравнимые с $2^k$

следовательно,



$\varphi_2(2^k)=2^k-2^{k-1}=2^{k-1}(2-1)=\frac 1 2 \cdot 2^k$ oтсюда



varphi_2(2^k\cdot\p_r^n\cdot p_s^t)= \frac 1 2 \cdot m\prod(1-\frac 1 {p_r})(1-\frac 1 {p_s})



Редактировалось 1 раз(а). Последний 30.07.2020 11:19.
25.08.2020 13:41
Re: Функции Эйлера высших порядков
Функции Эйлера высших порядков рассматривались ранее в этой теме применительно

к ПСВ по модулю M = p#. Теперь рассмотрим эти функции по любому составному модулю.

Естественным продолжением сортировки вычетов ПСВ является определение числа

групп вычетов (кортежей) в ПСВ по модулю р. Принцип тот же. Выбираем группу (кортеж)

с вычетами $а_1, а_2, а_3,.....а_n$ и вычитаем первый вычет из всего состава группы. Получим

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

группы с вычетами ПСВ.

$(0, d_1=a_2-a_1, d_2= a_3-a_1, d_3=a_4-a_1....d_(n-1)=a_n-a_1) или (0, d_1, d_2, d_3,...d_(n-1))$

Например, возьмем приведенную группу D[4] = (0, 2, 6, 8) и сравним ее с вычетами ПСВ по модулю $р = 5$.

0 - - - 2 - - - 6 - - - 8

1 - - - 3 - - - 7 - - - 9

2 - - - 4 - - - 8 - - - 10

3 - - - 5 - - - 9 - - - 11

4 - - - 6 - - -10 - - - 12

Как видим, только одна группа проходит по модулю $р = 5$. Это группа 1 - 3 - 7 - 9.

У остальных групп есть вычеты кратные $р = 5.$ Продолжим таблицу до модуля р = 7

5 - - -7 - - -11 - - -13

6 - - -8 - - -12 - - -14

Здесь проходят уже 3 группы. Вывод очевиден . Число таких групп в ПСВ по модулю $р$

равно $N(D[4]) = p - 4,$ где $4$ - число вычетов в группе. Однако, вернемся к модулю $р = 3.$

Здесь проходит одна группа, но по формуле не получается. В чем дело ?

А дело в том, что необходимо учитывать сравнимые вычеты группы по модулю $р$.

Среди вычетов группы нет сравнимых по модулям $р = 5$ и $р = 7$, но по модулю $р = 3$

имеем два сравнимых вычета 0 - 6 и 2 - 8. Сравнимые с $р$ вычеты группы в сумме

с любым вычетом ПСВ(р) не могут быть кратны $р$, а вычеты, сравнимые между собой

по модулю $р$ в сумме с вычетом группы оба становятся кратными $р$.

Они как-бы выпадают из состава группы, т.е. фактически "уменьшают" число вычетов группы.

Поэтому введем функцию $m(p)$ - число вычетов группы, сравнимых по модулю $р$

с каким-либо другим вычетом этой группы.

В случае с $р = 3$ имеем $m(3) = 2$, отсюда $N(D[4']) = 3 - (n - m(p)) = 3 - 2 = 1.$



Теперь мы можем дать определение функции Эйлера $n$ - го порядка.



Функция Эйлера $φ_n(р)$ $n$-го порядка определяет число групп вычетов (кортежей)

в ПСВ по модулю $р$, состоящих из $n$ вычетов взаимно простых с модулем $р$

и несравнимых по модулю $р.$

$φ_n(p) = p - n,$ при $p > n$, при $p ≤ n$, $φ_n(p) = 1.$

Доказательство.

Максимальное число взаимно простых вычетов по модулю р равно функции Эйлера φ(p).

Если число вычетов в группе n ≤ φ(p), то все они являются вычетами ПСВ по модулю р.

следовательно число таких групп равно

φ_n(p) = p - n

При n = φ(p), φ_n(p) = p - φ(p) = 1.

Если число вычетов в группе n > φ(p), то среди них будут сравнимые по модулю р,

но функция φ_n(p) их не учитывает, т.к. условия определения функции φ_n(p) не выполняются.

Чтобы остаться в рамках определения будем считать, что вычеты такой группы должны быть взаимно

простыми и несравнимыми по ближайшему простому модулю q > p. Тогда среди вычетов этой группы мы будем

иметь полные системы вычетов по всем p < q, следовательно, число вычетов группы, кратных

и сравнимых по модулю p будет равно m(p) = n - φ(p). отсюда число групп равно



p + n - φ(p) - n = 1. т.е. формально φ_n(p) = 1 при p ≤ n.





.



Редактировалось 1 раз(а). Последний 25.08.2020 18:57.
11.09.2020 11:34
: Функции Эйлера высших порядков
Функции Эйлера высших порядков мультипликативные., т.е.

$φ_n(p q) = φ_n(p) φ_n(q)$

Принимаем простые числа $р > n, q > n$. Вычеты группы взаимно простые с $p$ и $q$

и несравнимые по модулю $p$ и $q.$

Пусть х пробегает ($r_1, r_2,. . .r_p$ ) полную систему вычетов по модулю $p$, и

у пробегает($s_1, s_2, . . .s_q$) полную систему вычетов по модулю $q.$

Составим севозможные числа вида $p r_i + q s_j$ , соответствующие различным парам r_i и $s_j.$

Число таких чисел будет равно $p q$.

С другой стороны, т.к. $(p, q) = 1$, то эти числа образуют полную систему вычетов по модулю $p q$

Потенциально эти числа представляют собой первые вычеты групп n - го пордка, если среди

вычетов этих групп не будет чисел кратных $p$ и $q.$

Так как вычеты групп по определению взаимно простые числа, то в одной группе не может быть

двух вычетов кратных одному простому числу $p$ или $q$, но могут быть два вычета кратныx одно $р$,

другое $q$. Кроме того есть вычеты равные $p q$, число их равно $n.$

Число вычетов кратных $p$ в модуле $p q$ равно $q$ и наоборот. Отсюда общее число вычетов

кратных $p$ и $q$ во всех потенциальных группах $n$ - го порядка равно $(p + q) n$, но это при условии,

что в одной группе будет только один вычет, кратный $p$ или $q.$ Но это не так.

Вычеты кратные $p$ и $q$ будут располагаться в группах произвольно в различных комбинациях

среди n вычетов группы. Здесь мы имеем дело с перестановками 2- х вычетов кратных $p$ и $q$

в группе из $n$ вычетов. Их число вместе с числами pq равно

$n!/(n-2)! + n = n^2$

Отсюда, число групп n-го порядка в ПСВ по модулю $m = p q$ при принятых условиях равно

$φ_n(p q) = p q - ( p + q) n + n^2 = (p - n)(q - n) = φ_n(p) φ_n(q)$
12.09.2020 01:05
я не понял
а кто то эти простыни текста из ворда читает?
12.09.2020 08:44
между прочим
Цитата
vilfred
а кто то эти простыни текста из ворда читает?
Сам удивляюсь, откуда столько хитов и постов в данной теме.
16.09.2020 00:57
хм
для тех, кто еще не знакомы
с клоунами Бимом и Бомом,
сообщаю - эти шуты
фанатеют от простоты.

им обоим плевать на ковиды -
они оба видали виды.
им режим, не режим - все едино,
что на два и на три делимо.

каждый день несусветно талдычат
то про Эйлера, то про вычет,
про прогрессии и про модули
тычат рьяно друг в дружку мордами.

делать нечего на изоляции,
вот приходится и изголяться им -
ворошить цирковые опилки,
меж собой умножая цифирки.

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



Редактировалось 1 раз(а). Последний 16.09.2020 01:00.
16.09.2020 10:14
между прочем
Так вот откуда столько хитов и постов а данной теме.

Спасибо Дима.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти